CODEWITHSUNDEEP
prolog
Dragonslayer
Dragonslayer

Reputation: 65

Prolog seemingly ending recursive call without going back up

I've got the following two edges defined:

edge(a,b).
edge(b,c).

add(X, L, [X | L]).

Now I'm trying to recursively build the path from a to c (a,b,c) using this:

path(FROM,TO,W):-
    edge(FROM,TO),
    add(TO, [], X),
    add(FROM, X, W).
path(FROM,TO,W):-
    edge(FROM,Y),
    path(Y,TO, W),
    add(FROM, W, _).

It seems to work fine in the base case as path(a,b,X) will output X = [a,b]. However, path(a,c,X) only outputs X = [b,c], as if it just gets to the base case and ends it there rather than going back up the recursive call. Ultimately, I would like it to output X = [a,b,c] but I'm out of ideas.

FYI I'm using SWI-Prolog.

Upvotes: 0

Views: 89

Answers (2)

false
false

Reputation: 10102

How can you identify the problem yourself? There is an easy way to do so. First, identify the cases you expect to be true and cases you expect it to fail. Here are some plus some auxiliary definitions to ease debugging

:- initialization(path(a,b,[a,b])).
:- initialization(path(a,c,[a,b,c])).   % intended to be true, initially false
:- initialization(\+path(a,b,[a,_,c])).
:- initialization(\+path(a,d,_)).       % no node d, thus no path

:- op(950, fy, *).
:- meta_predicate(*(0)).

*_G_0.   % this permits us to remove goals by adding a * in front.

Now, save the program ..and say [program]. You will get a warning like

* user:user:path(a,c,[a,b,c]) - goal failed

So we know that we have not solved the problem.

Now, try to generalize the program by adding * in front of a goal. You will note that for each and every such generalization there will be more errors appearing (and in one case even non-termination). Except for the last goal where everything remains the same. So removing or replacing that goal seems to be a good idea.

Sooner or later you will encounter cycles. For acyclic paths, use path/4:

?- path(edge, Path, A, B).

Upvotes: 2

slago
slago

Reputation: 5509

Your code does not work correctly because it discards the result produced by the subgoal add(FROM, W, _), in the second clause of the predicate path/3. To solve the problem, you need to modify your code as following:

path(From, To, W):-
    edge(From, To),
    add(To, [], X),
    add(From, X, W).

path(From, To, PATH):-   
    edge(From, Y),
    path(Y,To, W),
    add(From, W, PATH). % <== get PATH

An even better version of this code is as follows:

path(From, To, [From, To]) :-
    edge(From, To).

path(From, To, [From|Path]) :-
    edge(From, X),
    path(X, To, Path).

Upvotes: 1

Related Questions