"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

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

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

You should pass the path as an accumulator. The CurrentState argument can be removed, because its content is included in the path so far (Path0 below).

Also, it's wiser to build up the path in reverse: a single reverse/2 call takes Θ(n) time. A single append/3 call takes time Θ(n) in the length of its second argument, so n calls to it take Θ(n²) time.

resolve(Start, Goal, Path) :-
    search(Goal, [Start], ReversePath),
    reverse(ReversePath, Path),
    writeln(finished).

search(GoalState, ReversePath, ReversePath) :-
    ReversePath = [GoalState|_].

search(GoalState, Path0, Path) :-
    Path0 = [CurrentState|_],
    suc(_, CurrentState, NextState, GoalState),
    Path1 = [NextState|Path0],
    search(GoalState, Path1, Path).

Answer 4

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.