Member in combination with recursion

Question

I learn Prolog at university and keep stumbling on someting rather odd during the home excercises. I wrote following Prolog clauses, which are part of a much bigger program:

edges(X,Edges):-
    findall(Edge,(highway(X,Y,Edge);highway(Y,X,Edge)),Edges).

edgesList([],_).
edgesList([node(X)|InL],OutL):-
    member((node(X),Edges),OutL),
    edges(X,Edges),
    edgesList(InL,OutL).

Which use following facts:

highway(1,2,yellow). 
highway(2,3,blue). 
highway(1,3,yellow).

You can see highway as a fact that describes two nodes in the first two arguments and an edge in the third. All facts together form a connected graph.

With the clause edgesList, I want to list the edges per node e.g.

Result = [(node(1),[yellow,yellow]),(node(2),[blue,yellow]),(node(3),[blue,yellow])]

But when I write my query:

edgesList([node(1),node(2),node(3)],List).

I get following result:

List = [(node(1),[yellow, yellow]), (node(2),[blue, yellow]), (node(3),[blue, yellow])|_G610]

For some reason, Prolog won't unify the tail of the result-list with the empty list, despite the fact that the member-predicate is used correct, I assume. It's something that happend a few times now in different excercises and it would be good to know what I did wrong...

There are essentially an infinite number of lists for which member((node(X),Edges),OutL) is true if OutL is a variable. At a Prolog prompt, see what happens if you do member(a, L). and press ; (see the next answer) after each result. Also, your base case edgesList([],_). is incorrect. _ doesn't mean nothing, but it means anything since _ is an anonymous variable. What does the edges list for [] look like? Surely it's not _ (anything). — lurker

coder coder · Accepted Answer · 2016-08-06T22:23:29

The problem is in the clause:

edgesList([],_).

because in the end it will fill the list with an uninstantiated tail (|_G610).

One solution is :

edges(X,Edges):-
    findall(Edge,(highway(X,Y,Edge);highway(Y,X,Edge)),Edges).

edgesList([],[]).
edgesList([node(X)|InL],[(node(X),Edges)|T]):-
   edges(X,Edges),
   edgesList(InL,T).

Member in combination with recursion

1 Answers