Writing an unnamed variable

Question

I am writing a program in Prolog (gprolog) that pathfinds on a graph. I based it partially off of this SO post.

Let me give an example. Here is an example graph I drew:

And here is what the code initially looked like:

path([Goal],Goal,Goal).
path(P,Start,Goal) :- adjacent(Start,X),
                      \+ (memberchk(X,P)),
                      (
                        Goal=X
                      ;
                        path([Start|P],X,Goal)
                      ).

Regardless of whether that base case is redundant, here is the problem. I want an input style of

| ?- path(P,a,f).

and for that input, I would get output of

P = [a,s,f]

true ?

However, the problem with the code as it stands lies with memberchk. For memberchk(a,P), it attempt to unify, calls memberchk(a,[a|_]), and returns true. I don't want this to happen, so I first check if P is instantiated using the var/1 predicate. Thus, my code changed to

path([Goal],Goal,Goal).
path(P,Start,Goal) :- var(P), 
                      path([],Start,Goal).
path(P,Start,Goal) :- adjacent(Start,X),
                      \+ (memberchk(X,P)),
                      (
                        Goal=X
                      ;
                        path([Start|P],X,Goal)
                      ).

Now if P is uninstantiated, we call path/3 with the empty list. My problem is this: now I cannot print P at the end, as I call path([],Start,Goal) and P is no longer associated with [].

I have tried using the write/1 predicate, but it either printed out P at every step or printed P = _26 (meaning it's printing the uninstantiated P, not the final value of P).

I hope this is a simple problem, I'm just awfully new to Prolog.

Apologies if something similar has been asked; I would love to be pointed to other questions that could help. I searched through SO and Google before posting this.

Please see [this question](http://stackoverflow.com/q/30328433/7473772). Maybe it shows a useful generalization? — , Mar 27 '17 at 09:06

score 2 · Answer 1 · answered Mar 27 '17 at 07:16

The concept you need is that of accumulators

You were actually very close: you realized indeed that initializing P to [], and filling it with [Start|P] as you recurse was a working strategy. This is called an accumulator, and to get the final result you simply need to add another argument.

Here is your new path/3 predicate that you query:

path(P, Start, Goal) :-
    path([], P, Start, Goal).

As you can see, here we add the [] as a first argument to path/4, which we implement like this:

path(L, P, Goal, Goal) :-
    reverse([Goal|L], P).
path(L, P, Start, Goal) :- 
    adjacent(Start, X),
    \+ (memberchk(X, L)),
    path([Start|L], P, X, Goal).

The first clause is here to terminate the recursion. Once the Start and Goal arguments are the same as you had noted, the recursion should be over. When using an accumulator this means that we unify the accumulator with the output argument. However, the accumulator contains the answer reversed (and lacks the final goal), so we have reverse([Goal|L], P).

The second clause is very similar to what you had written, with the exception that we now need to pass P as is to the recursive clause. Note that I have removed your disjunction in that clause, it isn't needed in that case.

The complete code:

path(P, Start, Goal) :-
    path([], P, Start, Goal).
path(L, P, Goal, Goal) :-
    reverse([Goal|L], P).
path(L, P, Start, Goal) :- 
    adjacent(Start, X),
    \+ (memberchk(X, L)),
    path([Start|L], P, X, Goal).

This has the same problem that I initially had: it relies on `memberchk(X, L)` which will unify and not work as intended. — Tyler Durden, Mar 28 '17 at 14:49
@TylerDurden Explain more clearly what "as intended" mean then, because as far as I can see it works for what you ask in the question. — Fatalize, Mar 28 '17 at 14:51
@Fatalize Ah, because you're starting `L` as the empty list, yours _does_ work as intended; I was mistaken. Thank you for the clarification. — Tyler Durden, Mar 28 '17 at 16:35

score 0 · Accepted Answer · answered Mar 28 '17 at 14:54

I solved my problem. The solution relies on:

Keeping track of visited nodes
When recursing, recursing on a smaller list
Checking if something is not a member of a list to prevent unification when not wanted

My code is as follows:

connected(X,Y) :- adjacent(X,Y);adjacent(Y,X).

not_member(_, []).
not_member(X, [Head|Tail]) :- X \== Head, not_member(X, Tail).

path(P,A,B):-path_helper(P,A,B,[Start]).

path_helper([X,Y],X,Y,_):-connected(X,Y).
path_helper([Goal],Goal,Goal,_).
path_helper([Start|[Head|P]],Start,Goal,Visited):-connected(Start,Head),not_member(Head,Visited),path_helper([Head|P],Head,Goal,[Head|Visited]).

Writing an unnamed variable

2 Answers2