CODEWITHSUNDEEP
prologdcg
devoured elysium
devoured elysium

Reputation: 105227

"Returning" a list from a predicate in Prolog

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?

Upvotes: 3

Views: 681

Answers (3)

gusbro
gusbro

Reputation: 22585

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.

Upvotes: 1

mat
mat

Reputation: 40778

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.

Upvotes: 5

Enigmativity
Enigmativity

Reputation: 117175

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

Upvotes: 0

Related Questions