Ancestor Problem

[Frisbeetarian]

Hey all, i am fairly new to Prolog and have had to teach myself the language off the internet as no one on campus had any experience working with Logic Programming.
My question present is a simple one, but it has dumbfounded me for the last 2 hours now. In an excercise, i am asked to find the ancestor of a node in a tree. I've written the code, but i just cant seem to make it give me the right answer.

The Ancestor clause is the one taken from Wikipedia after arduous labor on my Path clause. Ironically, none of the two works . Judging from the Ancestor clause i seem to have the logic pinned down but its syntax or misinformed programming that has held me down. Any help would be tremendously appreciated .

:- op(500, xfx, 'is_parent').
a is_parent b.  c is_parent g.
a is_parent c.  c is_parent h.
a is_parent d.  c is_parent i.
b is_parent e.  d is_parent j.
b is_parent f.  e is_parent k.

f is_parent l.
f is_parent m.
h is_parent n.
i is_parent o.
i is_parent p.
j is_parent l.
j is_parent r.
j is_parent s.
m is_parent t.

:- op(500, xfx, 'is_ancestor_of').
X is_ancestor_of Y:- ancestor(X,Y).

ancestor(A,B) :- A is_parent X,
	         ancestor(X, B).

path(K, Node) :- Mother is_parent Node,
	         path(K, Mother).

 

[kahleen]

Recursivity is a problem solving technique that relies on the fact that a solution for a given problem P(N) can easily be found if a solution for P(N - 1) is found. In some way or another, this idea can be applied to a great majority of the problems out there. So solving P(N) is done by first solving P(N - 1) and then adding some simple steps to achieve a solution for the entire P(N). But you have to be careful when using this technique, because if P(3) relies on P(2) and P(2) relies on P(1) and P(1) relies on P(0) and P(0) relies on P(-1) and so on ... you won't get anywhere. At some point, you must provide a solution that doesn't rely on recursivity. For example, if P(0) is simple enough, you can solve it without recursivity, then P(1) is also solved, then P(2) is also solved and so on.

In your case, you should provide the solution for the simple possible ancestor. When A is the parent of B, then A is also the ancestor of B. Your code never expresses that. It only states that A is an ancestor for B is A is the parent of X and X is the ancestor of B. So there are 2 different steps in every ancestor. But if A is the parent of B, these 2 steps do not exist, so you have to provide a special definition for this case. This is the solution for P(0) in terms of the discussion above.

ancestor(A, B) :-
    parent(A, B).
ancestor(A, B) :-
    A is_parent X,
    ancestor(X, B).

Why don't you use the 'is_ancestor_of' operator?

A is_ancestor_of B :-
    A is_parent B.
A is_ancestor_of B :-
    A is_parent X,
    X is_ancestor_of B.

Almost similar to natural language, right?

 

[Frisbeetarian]

May the gracious heavens brighten your destined path kind Sir, for you have brightened mine!
I now understand how this works, i thank you very much for the above explanation. I tried it with the code you provided and it works and is much clearer using close to natural language .
May i please inconvenience you with another question concerning the tree im working with?

Here is the whole code

:- op(500, xfx, 'is_parent').
a is_parent b.  c is_parent g.
a is_parent c.  c is_parent h.
a is_parent d.  c is_parent i.
b is_parent e.  d is_parent j.
b is_parent f.  e is_parent k.

f is_parent l.
f is_parent m.
h is_parent n.
i is_parent o.
i is_parent p.
j is_parent l.
j is_parent r.
j is_parent s.
m is_parent t.

:- op(500, xfx, 'is_sibling_of').
X is_sibling_of Y :- Z is_parent X,
                     Z is_parent Y,
                     X \== Y.

:-op(500, xfx, 'is_same_level_as').
X is_same_level_as X.
X is_same_level_as Y:- W is_parent X,
                       Z is_parent Y,
                       W is_same_level_as Z.

:- op(500, xfx, 'has_depth').
a has_depth 0:- !.
Node has_depth D:- Mother is_parent Node,
                   Mother has_depth D1,
                   D is D1 + 1.

locate(Node) :- path(Node),
                write(Node).

path(a).
path(Node) :- Mother is_parent Node,
              path(Mother),
              write(Mother),
              write(' --> ').

*****
height(N,H) :- setof(Z, ht(N,Z), Set),
               max(Set, 0, H).

ht(Node, 0) :- leaf(Node), !.
ht(Node, H) :- Node is_parent Child,
               ht(Child, H1),
               H is H1+1.

leaf(Node) :- not(is_parent(Node,child)).

max([], M, M).
max([X|R], M, A) :- (X > M -> max(R,X,A); max(R,M,A)).

The part below the **** is the one im having trouble understanding. The example just states the code without explanation and i do understand what "setof" does here. There are many variables inside of it which have had me confused for a while now. Everything below the asterisks is very blurry to be blurry to be honest.

 

[Frisbeetarian]

Do not understand what "setof" does here**.

 

[kahleen]

I believe you will be enlightened if you just try those predicates at the Prolog prompt and see how they behave.

'height' computes in variable H the height of a node N in the tree. For that, it uses 'ht', which computes the length of one path from a Node to a leaf descendant. Since there could be many paths from a Node to a leaf descendant in a tree, to compute the height of a node you need to gather all such distances returned by 'ht' in a list and take the maximum. This is what setof does: gathers in the list called Set all values of variable Z that satisfy ht(N, Z). If you take the maximum of the list Set you will obtain the height of N.

Try at the Prolog prompt these queries:

?- help(findall).
?- help(setof).
?- ht(a, Result).

After each value for Result, press the ';' key to obtain other values.

?- setof(Z, ht(a, Z), Set).

See the value of Set after the above query

?- height(a, Result).

Result = the maximum from the previous Set