“Returning” a list from a predicate in Prolog

Question

resolve(K, K, _) :- writeln('finished'). %goal state

resolve(CurrentState, GoalState, Path) :-
    suc(_, CurrentState, NextState, GoalState),
    append(Path, [CurrentState], NextPath),
    resolve(NextState, GoalState, NewPath).

I currently have this algorithm, and it works as it should. I am running it like this:

resolve(0, 10, Path).

I know for sure that the algorithm is running as it should, it gets to the goal state, although Path's value is

Path = []

which is not what should happen. Path should contain the sequence of "states" in which my algorithm has passed. What might be the problem?

Answer 1

It's easiest to use DCG notation to describe the list:

path(State0, Target) -->
    (    { State0 == Target } -> []
    ;    { suc(_, State0, State1, Target) },
         [State1],
         path(State1, Target)
    ).

You can also do it manually:

path(State0, Target, Path) :-
    (    State0 == Target -> Path = []
    ;    suc(_, State0, State1, Target),
         Path = [State1|Rest],
         path(State1, Target, Rest)
    ).

There is no need for accumulators here to get linear time.

Answer 2

I believe there is a problem in the way you want to build the Path. You might want to rewrite it so as to build it in the head of your predicate. Something like this:

resolve(K, K, []) :- writeln('finished'). %goal state
resolve(CurrentState, GoalState, [CurrentState|Path]) :-
    suc(_, CurrentState, NextState, GoalState),
    resolve(NextState, GoalState, Path).

The first clause ends the recursion: to go from state K to state K you return [] as the Path as you are already in the Goal state. The second clause builds the path, it gets the next state and calls recursively resolve, building the Path you have traversed when the recursion finishes.

Answer 3

Should the term NextPath in your append predicate be NewPath?

Currently there isn't any other usage of NextPath so Path must be binding to [] because NextPath is able to bind fully to [CurrentState].