Prologue and Fact Database
I am studying Prolog and I have some questions for you. I want to know how to do these problems, not the final solution.
As a beginner, I have so little knowledge about this language, but I don't want to be cheated :(
OK, so my question is ...
I have defined a binary tree like this:
tree(ID_of_tree,root,ID_left_tree,ID_right_tree)
For example, this tree
Defined as follows
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).
These are the facts in my fact database. So my first question is how to identify the father of node N in this database. For example:
?-father(3,a4,P). P=7 ?-father(6,a4,P). false
Definition of a 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 thought to use findall/3
, but I have 2 problems with this. One of them is returning a list and I want to get one number or false. And two, I don't know how to get to the base case if it needs to be done with recursion.
I think I need to use some predicates like retract or asserta, but I'm not sure about that.
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 try is like 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).
It may be fine, but I have a problem with this predicate like
father(3,d3,P). P = 7
I need to limit the search tree if Im looking in a subtree
Ok I finally got it. This is my attempt at last and works like a charm.
First of all, I created a predicate named check_tree/2
. This predicate checks if a tree is a subtree of another tree. For example:
?- check_tree(c4,c2).
false
?-check_tree(d1,b3).
true
This is the verification code:
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 then I define the parent predicate / 3 as follows:
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 the search subtree.
?- father(3,b3,P). P=7 ?- father(3,c4,P). false
Special thanks to luker and Will ness for the tips and their patience.
Thanks for reading this question.
source to share
You don't have to search the tree yourself - you already have your part (s) in your database. The prologue will search for it for you.
You already have
father1(3, a4, P):- % first approximation P = 7.
This is the first approximation to your predicate. Try:
? - father1 (3, a4,7).
true.
? - father (6, a4, P).
<B> is false.
Right! But the point is also 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 therefore also
father3(3, a4, P):- % third approximation tree(C2, 3, Nil, D2), ( tree(B3, P, C1, C2) ; tree(B3, P, C2, C1) ).
Can you see where I'm going with this?
Two remarks. First, why is this a representation and not just a term? Will your trees be separated by branches? Loops?
Secondly, a4
it is not used here. Why do you need this? Do you provide for duplicates in your tree and want to contain subtree searches?
But if this is not oversight on your part, and you really want to limit your search, you can increase the predicate father/3
to be used as a building block for this: continue looking for the father until you get to the one you are looking for (i.e. a4
in this case) - or not (i.e. did not collide with it on its way, which means that you are in the wrong part of the tree). You will need to tweak it to find not only the value but also the father ID (add a fourth argument to it).
edit: this is how you can do 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 the transitive closure of the extended predicate father4/4
wrt by its fourth argument, it would 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 is true
, you know you are in the correct subtree. You can code the conjuncture by hand, this is a good exercise to get a real feel for the language as well as the theoretical background. Think about how the student should complete each task before starting, and only then start learning complex tools that get the job done faster. Of course, the day will come when everything will be done with 3D printers, but until then (or even then) we can afford to view our trade as art.
But coding it by hand also gives you the ability to make it more efficient by stopping the search as soon as the parent id is found (if found):
is_under2(3, a4):- father4( 3, a4, P, B3), ( B3 == a4 , ! % a cut, if you would like it ; is_under( ... , ... ) ). % recursive call
Lets you use it under a different name.
Pay attention to the recursion: 3
is under a4
, if it a4
is a 3
father (called there B3
), or if the father 3
is under a4
. Makes complete sense, right?
source to share