Почему этот предикат Пролога не объединится?

Question

Я пишу предикат, чтобы найти все возможные состояния преемника для итерации A * и поместить их в список вроде [(cost, state), ...], который в настоящий момент стоит на этом месте:

addSuccessors(L, [], _).
addSuccessors(L, [X|T], OrigList) :- memb(OrigList, Index, X),
                                     add((X, Index), L, List2),
                                     addSuccessors(List2, T, OrigList).
addSuccessors(L, [X|[]], OrigList) :- memb(OrigList, Index, X),
                                     add((X, Index), L, L2),
                                     addSuccessors(L2, [], OrigList).

Add добавляет что-то в конец списка, memb получает (index) -ый элемент списка. Я знаю, что они работают, и когда я смотрю на L2 в нижнем предикате, я получаю что-то вроде этого

?- addSuccessors(X, [1500, 3670], [0, 0, 0, 1500, 3670]).
X = [] ;
[ (1500, 3), (3670, 4)]
X = [] ;
X = [_G1175] ;
[_G1175, (1500, 3), (3670, 4)]
X = [_G1175] ;
X = [_G1175, _G1181] ;
[_G1175, _G1181, (1500, 3), (3670, 4)]
X = [_G1175, _G1181] ;
...

Что очень расстраивает, потому что список [(1500, 3), (3670, 4)] - это то, что я хочу, чтобы X был после того, как я его назвал, так что похоже, что я делаю то, что хочу, только не ... где я хочу.

Пожалуйста, как мне это исправить?

Answer 1

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

Это может выглядеть примерно так, где addSuccessors_acc будет содержать предложения, которые вы уже определили.

addSuccessors(L, X, Y) :-
    addSuccessors_acc(L,[],X,Y).

Идея состоит в том, что второй аргумент предиката addSuccessors_acc действует как ваш накопитель, то есть список, который создается с каждым рекурсивным вызовом. Тогда в базовом случае предиката аккумулятора вам просто нужно объединить переменную аккумулятора с первым аргументом, чтобы передать окончательный список. например:

 addSuccessors_acc(L,L,_,_).

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

Answer 2

Прошло некоторое время с тех пор, как я запрограммировал на Прологе, но я думаю, что вам нужно отделить список, который вы строите, от списка, который вы возвращаете (т.е. добавьте еще один параметр). Ваше правило для [X | []] должно связывать выходную переменную, а не рекурсивно.