Перевести Haskell на Prolog - найти подсписок суммы

Question

Я пытаюсь перевести следующий код на Haskell:

-- sublistSums list sum returns a list of the sublists of list that add up to sum
sublistSums :: [Int] -> Int -> [[Int]]
sublistSums [] 0 = [[]]
sublistSums [] _ = []
sublistSums (x:xs) sum = [x:tailList | tailList <- sublistSums xs (sum-x)] ++
                         sublistSums xs sum

... в Пролог. Код должен дать мне список всех списков, чья сумма складывается в целевое число. Например,

?- sublistSums([[1,2,3],[4,5,6]],6).

Должен дать вам [[1,2,3]] если это связывает, потому что 1+2+3=6.

Это то, что я до сих пор:

sublistSums([], 0) :-
    sublistSums([],0,[]).
sublistSums([], _) :-
    sublistSums([],0,[]).
sublistSums([x|xs], sum) :-
    conc(conc(x,findall(xs,(sublistSums(xs, (sum-x))),List)), sublistSums(xs, sum)).

Однако когда я вызываю функцию sublistSums, это дает мне следующее:

?- sublistSums([[1,2,3],[4,5,6]],6).
false.

Я также попробовал:

sublistSums([], 0, ReList) :-
   [[]].
sublistSums([], _, ReList) :-
   [].
sublistSums([x|xs], sum, ReList) :-
   conc(conc(x,findall(xs,(sublistSums(xs, (sum-x)),ReList),List)), sublistSums(xs, sum, ReList)).

Тем не менее дает мне те же результаты. Не совсем уверен, что я здесь делаю не так.

Answer 1

В вашем коде Prolog есть несколько элементарных проблем:

• sum является атомом Пролога, поэтому он никогда не объединится со списком.
• в Прологе мы определяем отношения между сущностями, и вам нужны предикатные аргументы для ссылки на эти сущности.

Следовательно, вы не можете перевести этот код дословно. Тем не менее, вполне буквальный перевод на Haskell→Prolog возможен, если, например, вы введете новый аргумент для хранения возвращаемого значения исходной функции. Ваш второй фрагмент идет в этом направлении, но он не является автономным, а также содержит несколько ошибок. Например xs а также sum являются атомами, тогда как переменные Prolog начинаются с заглавной буквы или с подчеркивания.

Кроме того, если вы продолжите попытки буквального перевода, вы упустите возможность по- настоящему извлечь выгоду из общности отношений. Типичные предикаты Prolog могут использоваться не только в одном, но и в нескольких направлениях, и вы можете использовать их не только для вычисления, но также для проверки и для завершения частичных результатов.

---

Таким образом, вместо буквального перевода, я хотел бы показать вам более идиоматическое решение Пролога этой задачи.

Наше первое наблюдение, которое ясно из сигнатуры типа: мы рассуждаем над целыми числами. Таким образом, я рекомендую вам использовать ограничения CLP(FD) вашей системы Prolog для полностью декларативной целочисленной арифметики. Смотрите clpfd для получения дополнительной информации об этой функции.

Во-вторых, задачу можно рассматривать как "фильтрацию" списка, и для этого мы используем tfilter/3 который предоставляется библиотекой (Рейф).

Вот полное решение Prolog:

sublist_sum (Lss0, Sum, Lss): -
        tfilter (sum_intlist (Sum), Lss0, Lss).

sum_intlist (Sum, Ls, T): -
        сумма (Ls, #=, Sum0),
        zcompare(C, Sum0, Sum),
        eq_truth(C, T).

eq_truth(=, правда).
eq_truth (<, false).
eq_truth (>, false).

Думайте об этом предикате как о связывании списка Lss0, сумма и второй список Lssтак, что все предъявляемые вами требования выполнены. Обратите внимание, что я не говорю, какой из этих аргументов "дан", потому что любой из них может быть полностью, частично или вообще не указан.

Ваш пример работает как требуется:

? - sublist_sum ([[1,2,3], [4,5,6]], 6, Ls).Ls = [[1, 2, 3]].

Этот пример находится в пределах исходной функции: первый и второй аргументы полностью определены, а третий используется для представления "результата".

Однако, как это типично для Пролога, мы можем также выполнять более общие запросы, в которых не указывается не только "результат", но и другие части. Понятно, что это выходит за рамки функций, и буквальный перевод исходного кода может не иметь этого преимущества.

Например:

? - sublist_sum ([[1,2,N]], 6, Ls).

В этом случае мы оставили N не уточняйте и попросите Пролог рассмотреть все случаи, которые могут N,

В ответ Пролог генерирует различные возможности, представленные как дизъюнкция:

N = 3, Ls = [[1, 2, 3]];
Ls = [],N в инф..2,-3 + _10694 # = N,
_10694 в инф..5;
Ls = [],N в 4..sup,-3 + _10662 # = N,
_10662 через 7 дней

Обратите внимание, как Ls зависит от N,

Мы можем также обобщить это далее, и оставить даже сумму без указания:

? - sublist_sum ([[A, B, C]], Sum, Ls). Ls = [[A, B, C]],
A + B + C# = Сумма;
Ls = [],
А + В + С # = _ 15806,
_15806 # = , _15806, Sum).

И снова Пролог перечисляет разные случаи.

Более того, мы можем специализировать запрос и использовать его для проверки отношения:

? - sublist_sum ([[1,2,3]], 5, []).правда.

Здесь мы спросили: имеет ли место этот конкретный случай? и Пролог отвечает true, указывая, что отношение работает именно так, как и предполагалось в этом случае.