Why won't this Prolog predicate unify?

Question

Hi,

I'm writing a predicate to find all possible successor states for an iteration of A* and put them in a list like [(cost, state), ...] , which stands at this at the moment:

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 adds something to the end of a list, memb gets the (index)th element of a list. I know they work, and when I look at L2 in the bottom predicate I get something like this

?- 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] ;
...

Which is very frustrating because the [(1500, 3), (3670, 4)] list is what I want X to be after I call it so it looks to be doing what I want just not... where I want.

Please, how can I fix this?

Answer 1

It's been awhile since I programmed in Prolog, but I think you need to separate the list that you are building up from the list that you return (i.e., add another parameter). Your rule for [X|[]] should bind the output variable and not recurse.

Answer 2

Think about how L actually gets it's initial value. Well the thing is it doesn't. What you're trying to do is build up a list from scratch, so you need to start with an empty list, not an unbound variable. One way to solve this is to write a wrapper predicate which allows your current predicate to act as an accumulator predicate.

This might look something like this, where addSuccessors_acc will contain the clauses that you have already defined.

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

The idea is that the second argument to the addSuccessors_acc predicate acts as your accumulator, which is the list that is being built up with each recursive call. Then in the base case of the accumulator predicate you just need to unify the accumulator variable with the first argument, to pass along the final list. eg:

 addSuccessors_acc(L,L,_,_).

Also, as ergosys points out, your third clause can actually be the base case. Since you are dealing with the last element in the list there is no need to recurse - all that is doing is delaying the base case one extra call onwards.