How can I avoid this pitfall in my Prolog recursion?

Question

My objective is to be able to traverse nodes in a diagram and output the length of the path in Prolog. I'm using recursion and I'm stuck on this issue. Here's my attempt so far.

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

distance(X,Y,1) :- edge(X,Y).
distance(X,Y,Dis) :- edge(X,Z), distance(Z, Y, D), Dis is D +1.

Issue: I'd like to be able to say Dis = 0. if the path is invalid. As in, there is no edge connecting the two nodes, Dis = 0. Currently my code says false for an invalid path. My attempts in this endeavor have lead to me breaking the recursion. Thanks for any help.

Are you sure about the semantics of distance? Wouldn't Dis = 0 imply that the two nodes are the same? This could be coded as distance(X,X,0). — Hashcut

Fatalize Fatalize · Accepted Answer · 2017-01-31T08:30:59

As @Hashcut says in his comment, it would make more sense that if Dis = 0, then X = Y. It is in fact perfectly logical that your predicate would fail if the path is invalid.

Now if you really want to do what you say, you can do it as such:

distance_(X,Y,1) :- edge(X,Y).
distance_(X,Y,Dis) :- edge(X,Z), distance_(Z, Y, D), Dis is D + 1.

distance(X,Y,D) :- distance_(X,Y,D) -> true ; D = 0.

We simply rename your original predicate into distance_, and then create the predicate distance which does the same as before if the path exists, or unify D with 0 if it fails. -> is used to discard the choice D = 0 if the path is valid.

Note that you have this behavior:

?- distance(a,a,X).
X = 0.

?- distance(b,f,X).
X = 0.

Which is kind of weird, but expected because of what you want.

How can I avoid this pitfall in my Prolog recursion?

1 Answers