Prolog homework help.

Question

Okay, my last prolog question. It's the common geneaology problem.

I am suppose to take a list of facts and have a function called descendant that will return a list that has all the descendants. For example:

Given the rules:

parent('Bob', 'Tim').
parent('Joe', 'Bob').

The function call:

    descendant('Joe', X).

should return:

        X = ['Bob', 'Tim'].

I can get it to return the immediate descendant of 'Joe' but not the full line. Here's what I have.

 % Recursive case
  descendant(X,DList) :- parent(X,A), NewDList = [A|DList], 
                         descendant(A, NewDList).
 % Base case, I have a feeling this is wrong.
  descendant(_,[]).

This code only seems to return true or false, or just an empty [].

I could use some help on what I might need to look at. Thanks.

Answer 1

My Prolog is a bit rusty and I'm loathe to post an answer to such a problem - you won't learn much that way.

I'll just point out that you shouldn't have that assignment statement in there - NewDList = [A|DList] - this is considered bad form in the Prolog style of programming - assignments should only be used where there is not a "pure" logical solution - certainly not the case here.

Cheers, Craig.

Answer 2

parent('Bob', 'Tim').
parent('Joe', 'Bob').

descendant(X,[H|T]) :- parent(X,H), descendant(H, T).
descendant(X,[]) .

returns

?- descendant('Joe', L).
L = ['Bob', 'Tim'] ;
L = ['Bob'] ;
L = [].

actually it is hard to write predicate that will return only ['Bob', 'Tim'] because list ['Bob'] is also valid. if you decide to leave only longest chain it gets too comlicated

if i understood question incorrectly here is one version:

desc(X, A) :- parent(X,H), desc(H, A).
desc(X, A) :- X = A.

Answer 3

Firstly, we'll create a predicate that can finds a single descendant.

descendant(X, Y) :- parent(X, Y).
descendant(X, Y) :- parent(X, Z), descendant(Z, Y).

We can then use the findall predicate to list all descendants:

descendants(X, L) :- findall(A, descendant(X, A), L).

So, for instance:

parent(bob, tim).
parent(joe, bob).
parent(joe, mary).

descendant(X, Y) :- parent(X, Y).
descendant(X, Y) :- parent(X, Z), descendant(Z, Y).

descendants(X, L) :- findall(A, descendant(X, A), L).

gives:

?- descendants(joe, X).
X = [bob, mary, tim].