CODEWITHSUNDEEP
prolog
Bishop19
Bishop19

Reputation: 47

Can I use integers as parameters?

How can I know if a person X is descendant of a person Y given the descendancy degree?

I've tried this:

descendant(X, Y, 1) :- son(X, Y).
descendant(X, Y, Degree) :- son(X, Z) , descendant(Z, Y, Degree-1).

Where son(X, Y) returns yes if X is son of Y. If Degree == 1 it returns the correct answer but for descendant(X, Y, 2), for instance, should return yes if X is grandson of Y but returns no.

Upvotes: 1

Views: 74

Answers (2)

repeat
repeat

Reputation: 18726

1) Naming: Does son(X,Y) mean "X is the son of Y"—or vice-versa? son_of(X,Y) is better.

2) Exploit : We don't need to do general arithmetics here... we only need to count.

So let's start in the beginning...

child_of(abel, adam).           % from source
child_of(abel, eve).
child_of(cain, adam).
child_of(cain, eve).
child_of(enoch, cain).
child_of(irad, enoch).
child_of(mehujael, irad).
child_of(methushael, mehujael).
child_of(lamech, methushael).
child_of(jabal, lamech).
child_of(jabal, adah).
child_of(jubal, lamech).
child_of(jubal, adah).
child_of(tubal_cain, lamech).
child_of(tubal_cain, zillah).
child_of(naamah, lamech).
child_of(naamah, zillah).
child_of(seth, adam).
child_of(seth, eve).
child_of(enos, seth).
child_of(kenan, enos).
child_of(mahalalel, kenan).
child_of(jared, mahalalel).
child_of(enoch, jared).
child_of(methuselah, enoch).
child_of(lamech, methuselah).
child_of(noah, lamech).
child_of(shem, noah).
child_of(ham, noah).
child_of(japheth, noah).

Based on child_of/2 we first define ancestor_of/2—this should be nothing new to you!

ancestor_of(Y, Z) :-
   child_of(Z, Y).              %   If Z is  a    child of Y ...
                                % then Y is an ancestor of Z.
ancestor_of(X, Z) :-
   child_of(Z, Y),              %   If Z is  a    child of Y ...
   ancestor_of(X, Y).           %  and X is an ancestor of Y ...
                                % then X is an ancestor of Z.

Next, we add an additional parameter indicating the distance.

We use s/1 terms to represent natural numbers and add a new argument to ancestor_of/2:

ancestor_of_dist(Y, Z, s(0)) :-      
   child_of(Z, Y).              %   If Z is  a    child of Y ... 
                                % then Y is an ancestor of Z with distance = 1."
ancestor_of_dist(X, Z, s(N)) :-      
   child_of(Z, Y),              %   If Z is  a    child of Y ... 
   ancestor_of_dist(X, Y, N).   %  and X is an ancestor of Y with distance N ...
                                % then X is an ancestor of Z with distance N+1.

So ... who is grandparent of whom?

?- ancestor_of_dist(X, Z, s(s(0))).
   X = adam, Z = enoch
;  X = eve, Z = enoch
;  X = cain, Z = irad
;  X = jared, Z = irad
;  X = enoch, Z = mehujael
;  ... 
;  X = lamech, Z = japheth
;  false.

Upvotes: 5

Paulo Moura
Paulo Moura

Reputation: 18683

Prolog is not a functional language. Thus, the Degree-1 term is not interpreted and evaluated as an expression. For Prolog, Degree-1 is just a compound term with two arguments. That can be made clear using the standard write_canonical/1 predicate, which writes a term without using operator notation:

?- write_canonical(Degree-1).
-(_,1)
true.

Write instead:

descendant(X, Y, 1) :-
    son(X, Y).
descendant(X, Y, Degree) :-
    son(X, Z) ,
    descendant(Z, Y, Degree0),
    Degree is Degree0 + 1.

The is/2 standard built-in predicate unifies the left argument with the value of the arithmetic expression in the right argument.

P.S. Note that the alternative descendant/3 predicate definition I suggest will solve the problem you described but it is not an efficient definition as it is not a tail-recursive definition. I.e. the recursive call in the second clause is not the last call in the clause body. This issue can be easily solved, however, by using an accumulator.

Upvotes: 3

Related Questions