Prolog: Make a list in recursion to a variable

Question

I'm writing a rule that is to go from one node to a destination in a cyclic graph. In order to do this I need the rule to remember the visited nodes as it moves through the graph. My problem is that I want to be able to call it like this:

?- routeToDestination(startNode, destinationNode, Path)

and get the path through the graph stored in the Path variable. When I try to append the nodes in the Path variable I'm having some troubles with it not being initiated as a list. My rule looks like this so far:

routeToDestination(Destination, Destination, Path).
routeToDestination(Origin, Destination, Path):-
    link(Origin, Via),
    \+ visited(Via, Path),
    appendEnd(Path, Via, Result),
    routeToDestination(Via, Destination, Result).

Here link is a number of facts that tell where there are connections from Via (i.e. I check to which nodes I can go from Via), visited checks if the element is already in the Path (don't want to visit twice), appendEnd is the typical append function (http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/lists.html):

append([],List,List).
append([Head|Tail],List2,[Head|Result]):-
    append(Tail,List2,Result).

Whenever I try to make the call it looks like the append function fails because Path is a variable and not a list. Is there a workaround for this, or am I thinking the wrong way?

Magic trick: If `Via` is any term, then `[Via]` is a list with a single element. But using `append/3` is often an indication of a problem with your approach. Either *prepend* the element, using for example: `Path = [Via|Path0]` and *reverse* the path at the end, or use [tag:dcg] to build the list much more efficiently. — mat, May 11 '16 at 09:41
Thanks, prepending seems alot easier! But is it possible to have the list "returned" as Path in the end, so I can use it outside the rule? — user3741158, May 11 '16 at 10:40
Sure: As I said, either use [tag:dcg] to conveniently describe the list, or use a relation of the `route_to_destination(Origin, Destination, Path0, Path)`, where `Path0` is used to build the path *in reverse*, and the base case simply states `reverse(Path0, Path)` to reverse it. — mat, May 11 '16 at 11:05

score 0 · Answer 1 · answered May 11 '16 at 23:49

A very common idiom in Prolog is the use of helper predicates that carry 1 or more additional arguments that maintain state for you. Often, such helpers will have the same name with a different arity.

In that mode, given a directed graph that's defined something like this:

link(a,b).
link(a,c).
link(b,d).
link(d,a).

One might traverse it thusly:

connected( A , B , P ) :-
  setof(X,link(X,_),As) ,
  member(A,As) ,
  connected(A,B,[],P) ,
  .

connected( B , B , V , P ) :-
  reverse(V,P)
  .
connected( A , B , V , P ) :-
  link(A,X) ,
  \+ member(X,V) ,
  connected(X,B,[A|V],P)
  .

Prolog: Make a list in recursion to a variable

1 Answers1