Prolog and facts database

Question

Im learning Prolog and I have some questions for you. I want to learn how to do these problems not the final solution.

As a newbie I have so little knowledge about this language but I dont want to be a cheater :(

OK so my question is...

I have define a binary tree like this:

tree(ID_of_tree,root,ID_left_tree,ID_right_tree)

For example, this tree

Is defined like this

tree(a4,6,b3,b4).
tree(b3,7,c1,c2).
tree(c1,5,d1,nil).
tree(d1,1,nil,nil).
tree(c2,3,nil,d2).
tree(d2,4,nil,nil).
tree(b4,8,c3,c4).
tree(c3,10,nil,nil).
tree(c4,11,d3,d4).
tree(d3,9,nil,nil).
tree(d4,2,nil,nil).

They are facts in my facts database. So my first question is, how to identify the father of a node N in this database. For example:

?-father(3,a4,P).
P=7
?-father(6,a4,P).
false

Defining predicate father/3.

father(N,Abn,P).

N= Node that I want to get its father
Abn = Tree where Im looking for. If a4, this means that is the all tree in this case.
P = Father of N.

I was thinking to use findall/3 but with this I have 2 problems. One this returns a list and I want to get a single number or false. And two, I dont know how to get to the base case if this must be done with recursion.

I think that I need to use some predicates like retract or asserta for example but Im not sure about this.

This is my first attempt but the output using father(3,a4,P). is false

father2(N,Abn,PA,PA):- =(N, PA).
father(N,Abn,P) :- tree(Abn,N,A1,_), tree(A1,PA,_,_), father2(N,A1,PA,P).
father(N,Abn,P) :- tree(Abn,N,_,A2), tree(A2,PA,_,_), father2(N,A2,PA,P).

My second attempt is this and it returns a good solution

father(N,Abn,P):- tree(FT,N,_,_), tree(_,P,FT,_).
father(N,Abn,P):- tree(FT,N,_,_), tree(_,P,_,FT).

This could be good but I have a problem with this predicate for example

father(3,d3,P).
P = 7

I should limit the search tree if Im looking in a subtree

Ok, finally I got it. This is my finally attempt and working like charm.

First of all I created a predicate named check_tree/2 . This predicate check if a tree is a subtree of other tree. For example:

?- check_tree(c4,c2).
false

?-check_tree(d1,b3).
true

This is the code for the check:

check_tree(Abn1,Abn1).
check_tree(Ab1,Ab2):- tree(Ft,_,Ab1,_), check_tree(Ft,Ab2).
check_tree(Ab1,Ab2):- tree(Ft,_,_,Ab1), check_tree(Ft,Ab2).

And next I define the predicate father/3 like this:

father(N,Abn,P):- tree(FT,N,_,_), tree(_,P,FT,_), check_tree(FT,Abn).
father(N,Abn,P):- tree(FT,N,_,_), tree(_,P,_,FT), check_tree(FT,Abn).

Now I only calculate the father if the node is inside of the search subtree.

?- father(3,b3,P).
P=7

?- father(3,c4,P).
false

Special thanks to luker and Will ness for the hints and their patience.

Thanks anyway for read this question.

Answer 1

You don't need to search in a tree yourself - you already have it taken down to pieces (nodes) in your database. Prolog will search it for you.

You already have

father1(3, a4, P):-             % first approximation
    P = 7.

This is the first approximation to your predicate. Try it:

?- father1(3,a4,7).
true.
?- father(6,a4,P).
false.

Correct! But it is also the case that

father2(3, a4, P):-              % second approximation
    tree(c2,3,nil,d2), 
    ( tree(b3,7,c1,c2) ; tree(b3,7,c2,c1) ), 
    P = 7.

and so, also

father3(3, a4, P):-               % third approximation
    tree(C2, 3, Nil, D2), 
    ( tree(B3, P, C1, C2) ; tree(B3, P, C2, C1) ).

Do you see where I'm going with this?

Two remarks. First, why this representation, and not just as a term? Will your trees have shared branches in them? Cycles?

Second, a4 isn't used here. Why should you need it at all? Do you envisage duplicates in your tree and want to restrain your search to a sub-tree?

But if this isn't an oversight on your part, and you really do want to constrain your search, you can augment the above father/3 predicate to be used as a building block for this: continue searching for a father until you hit the one you're searching for (i.e. a4 in this case) -- or not (i.e. did not encounter it on your way up, meaning you're in the wrong part of the tree). You'll need to tweak it to find not only the value, but also the ID of the father (add a fourth argument to it).

---

edit: Here's how you could go about it:

father4(Three, A4, P, B3):-               % fourth approximation
    tree(C2, Three, Nil, D2), 
    ( tree(B3, P, C1, C2) ; tree(B3, P, C2, C1) ).

Then, if you formed a transitive closure of the extended father4/4 predicate w.r.t. its fourth argument, it'd be as simple as

is_under1(3, a4):- 
    transitive_closure(father4(3, a4, _), List_Of_IDs),      % pseudocode
    memberchk(a4, List_Of_IDs).

and then if it's true, you know you're in the correct subtree. You can code the conjunction by hand, it's a good exercise to get yourself a real feel for the language as well as the theoretical foundations. Consider how an apprentice must do every menial task by hand first, when they start, and only then proceed to learning the complex tools that do the job quicker. Of course a day will come when everything will be done by 3D printers, but until then (or even then), we can indulge in treating our trade as an art.

But coding it by hand also gives you a chance to make it more efficient, stopping the search as soon as the parent ID is found (in case that it is found):

is_under2(3, a4):-
    father4( 3, a4, P, B3),
    ( B3 == a4 , !                   % a cut, if you would like it
    ; is_under( ... , ... ) ).       % recursive call

Calling it by different name helps.

Notice the recursion: 3 is under a4 if a4 is 3's father (called B3 there), or if the 3's father is under a4. Makes total sense, right?