Prolog GNU - Having a difficult time with this, lists and recursion

Question

So , i still don't completely understand how lists and recursion work in prolog, could be why i am having trouble with this, but i don't even know how to begin this problem.

There is a list of friends.

f(a,b).
f(a,c).
f(a,d).
f(b,c).
f(b,e).
f(b,f).
f(c,e).
f(c,g).
f(g,e).
etc..

I have to find if someone is a friend through someone else up to two friends of friends.

So example if i did

fof(a,e, List).

Then i should get

List = [a, b, e];
List = [a, c, e];
List = [a, c, g, e]; <-- anything past this point won't work

So basically you check yourself, then see if your friends is friends with person2, then see if their friends are friends with person2, if they are then add to a list.

not exactly sure how to execute this though.

Ok, so i got something similar to what i need.

fb(X,X,_).
fb(X,Y,List) :- 
    friend(X,Y),
    X \== Y,
    List = [X,Y].
fb(X,Y,List) :-
    friend(X,Z),friend(Z,Y),
    X \== Y, X \== Z, Z \== Y,
    List = [X,Z,Y].
fb(X,Y,List) :-
    friend(X,Z),friend(Z,Q),friend(Q,Y),
    X \== Y,X \== Z, X \== Q, Z \== Q, Z \== Y, Q \== Y,
    List = [X,Z,Q,Y].

This seems to work, but it seems i could condense this with recursion, just not sure how.

Answer 1

I assume you've defined friend(X,Y) to be true if either f(X,Y) or f(Y,X).

Your problem can be solved recursively by adding an argument that specifies the maximum path length allowed, and decrementing that before each recursive call.

fof(X,X,[X],_).
fof(X,Z,[X|Path],N) :-
    N >= 1,
    friend(X,Y),
    M is N-1,
    fof(Y,Z,Path,M),
    \+ member(X,Path).  % no duplicates

To get to a friend of a friend via max. two intermediaries, i.e. in three steps:

?- fof(a,e,L,3).
L = [a, b, c, e] ;
L = [a, b, e] ;
L = [a, c, e] ;
L = [a, c, g, e] ;
L = [a, c, b, e] ;
false.

?- fof(a,z,L,3).
false.