Функция поиска списка в прологе

Question

Я новичок в Prolog и пытаюсь написать функцию, которая находит список, который следует некоторым правилам. Более конкретно, учитывая два числа, N и K, я хочу, чтобы моя функция находила список с K степенями двойки, сумма которых равна N. Список должен содержать не каждую степень, а общую сумму каждой степени. Например, если N = 13 и K = 5, я хочу, чтобы мой список был [2,2,1], где первые 2 означают два 4, вторые 2 означают два 2, а третье 1 означает один 1 (4 + 4 + 2 + 2 + 1 = 13). Учтите, что начиная с конца списка каждая позиция i представляет степень 2 ^ i. Итак, я написал этот код:

sum2(List, SUM, N) :-
   List = []  -> N=SUM;
   List = [H|T],
   length(T, L),
   NewSUM is SUM + (H * 2**L),
   sum2(T, NewSUM, N).

powers2(N,K,X):-
   sum2(X,0,N),
   sum_list(X, L),
   K = L.

Проблема:

?- sum2([2,2,1],0,13).
true.
?- sum2([2,2,1],0,X).
X = 13.
?- sum2(X,0,13).
false.
?- powers2(X,5,[2,2,1]).
X = 13.
?- powers2(13,5,[2,2,1]).
true.
?- powers2(13,X,[2,2,1]).
X = 5.
?- powers2(13,5,X).
false.

In В случаях, X представляет список, который, как я ожидал, будет списком, который следует правилам, а не false. Не могли бы вы помочь мне найти, как я могу решить эту проблему и получить список для вывода в этих случаях?

Answer 1

Непосредственная причина отказа вашего предиката с несвязанным списком связана с использованием вами конструкции -> для потока управления.

Вот упрощенная версия того, что вы пытаетесь сделать, небольшой предикат для проверки, является ли список пустым или нет:

empty_or_not(List, Answer) :-
    (   List = []
    ->  Answer = empty
    ;   List = [H|T],
        Answer = head_tail(H, T) ).

(Примечание: точный макет - дело вкуса, но вы должны всегда заключать код в круглые скобки если вы используете оператор ;. Я также призываю вас никогда не ставить ; в конце строки, а лучше в таком месте, где он действительно выделяется. Использование ; действительно исключительное case в Prolog, и если он отформатирован слишком похоже на ,, может быть трудно увидеть, что он вообще есть, и к каким частям предложения он применяется.)

И это, кажется, работает, верно ?

?- empty_or_not([], Answer).
Answer = empty.

?- empty_or_not([1, 2, 3], Answer).
Answer = head_tail(1, [2, 3]).

Хорошо, но что, если мы вызовем это с помощью несвязанного списка?

?- empty_or_not(List, Answer).
List = [],
Answer = empty.

Вдруг принимается только пустой список, хотя мы знаем сверху, что непустые списки a re тоже в порядке.

Это потому, что -> отсекает любые альтернативы, как только обнаруживает, что его условие выполнено. В последнем примере List - это переменная, поэтому она унифицирована с []. Условие List = [] будет выполнено успешно (привязка List к []), и альтернативный вариант List = [H|T] не будет использоваться. Это кажется простым, но -> на самом деле является расширенной функцией Prolog. Его должны использовать только более опытные пользователи, которые знают, что им действительно не нужно будет исследовать альтернативы.

Обычный и обычно правильный способ реализации дизъюнкции в Prolog - использовать отдельные предложения для отдельных case:

empty_or_not([], empty).
empty_or_not([H|T], head_tail(H, T)).

Теперь это ведет себя логически:

?- empty_or_not([], Answer).
Answer = empty.

?- empty_or_not([1, 2, 3], Answer).
Answer = head_tail(1, [2, 3]).

?- empty_or_not(List, Answer).
List = [],
Answer = empty ;
List = [_2040|_2042],
Answer = head_tail(_2040, _2042).

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

sum2([], SUM, N) :-
    N = SUM.
sum2([H|T], SUM, N) :-
    length(T, L),
    NewSUM is SUM + (H * 2**L),
    sum2(T, NewSUM, N).

Это это всего лишь небольшой шаг:

?- sum2(X, 0, 13).
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:    [9] _2416 is 0+_2428* ...
ERROR:    [8] sum2([_2462],0,13) at /home/gergo/sum.pl:5
ERROR:    [7] <user>

Вы пытаетесь произвести арифметику c на H, которое не имеет значения. Если вы хотите использовать "простую" арифметику c Пролога, вам нужно будет перечислить соответствующие значения, которые может иметь H, прежде чем вы попытаетесь выполнить над ней арифметию c. В качестве альтернативы вы можете использовать ограничения arithmeti c. См. Возможные реализации обоих в Арифметика в Прологе, представьте число с использованием степени 2 .