CODEWITHSUNDEEP
prolog
am3decoy
am3decoy

Reputation: 73

Recursion in PROLOG?

Given the following Prolog facts:

f(a, [b]).
f(b, [c]).
f(c, [d]).
f(d, [e]).
f(e, []).

I need to create a query xyz(a,Y) so that I get Y = [e,d,c,b], since a depends on b, which depends on c, etc. My current query is:

xyz(X,Y):-
  f(X,P),
  member(Y,[P]).

However, this query for xyz(a,Y) only gives me Y = [b], and not b's dependents, etc.

I figured that perhaps I can add these two lines to the end of the query above, but that doesn't work as I would like it to. Since the previous free query successfully retrieves a's dependent b, I was hoping these next two lines could perhaps do the same for b and on. But, I don't think this is a good way to approach it maybe. Maybe recursion is a better idea.

f(P,S),
member(Y,[P]).

I'm pretty sure that I should add a recursion in the end, but I am not sure how to approach. Can someone help me please?

(3/4) Edit:

I was able to successfully solve the issue of single-element lists with @CapelliC approach below. However, I would like to extend this problem so that it works for multiple-element lists, where the Prolog facts now look like:

f(a, [b, d]).
f(b, [c]).
f(c, []).
f(d, [e]).
f(e, [f]).
f(f, [g).
f(g, []).

In this case, query of xyz(a,X) should give me: X = [b,c,d,e,f,g], the element-order doesn't necessarily matter, I can sort that after.

This was the previous code that works for single-lists:

xyz(Z, [X|Y]):-
    f(Z,[X]),
    !,
    xyz(X,Y).
    xyz(_,[]).

According to @lurker I need to incorporate the member function, but I am having trouble with it. This is my current approach, but it doesn't work and just gives me an empty list as output for everything:

xyz(Z, [X|Y]):-
    f(Z,X),
    member(Y,X), // I'm not sure if this should be a 'Y'
    !,
    xyz(X,Y).
    xyz(_,[]).

Any ideas?

Upvotes: 2

Views: 349

Answers (1)

CapelliC
CapelliC

Reputation: 60004

this snippet get the list in reverse order, wrt your request...

xyz(K, [D|Ds]) :- f(K, [D]), !, xyz(D, Ds).
xyz(_, []).

edit extending to multiple dependency elements (but without loops !) could be done like

xyz(K, Ds) :- f(K, DKs) -> findall([T|P], (member(T, DKs), xyz(T, P)), L), flatten(L, F), sort(F, Ds) ; Ds = [].

Upvotes: 1

Related Questions