Prolog and facts database

[Juan]

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

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.

Thanks anyway for read this question.

[Barb Knox]

On 10 Jun 2017, at 05:48, Juan <juaan...@gmail.com> wrote:

I[']m 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 don't want to be a cheater :(

That's a good attitude (especially since few if any will want to do your homework for you).

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

<https://lh3.googleusercontent.com/-uCagayzlViI/WTrfHnqpbjI/AAAAAAAAA2A/ZeSTiX5fKTQ5BY7Hb5wtmqSbm_Ndm3sBwCLcB/s1600/Selection_008.png>

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).

The first and second arguments contain identical information, so one of them is redundant.  Since your tree picture uses numbers for the node names, I suggest you get rid of the first argument and replace each reference to it with the appropriate node number, e.g.:

tree(6, 7, 8).

tree(7, 5, 3).

...

Your nil node might then be the number 0.

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

These queries would then be father(3, 6, P) and father(6, 6, P).

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 don[']t know how to get to the base case if this must be done with recursion.

Those are two very good reasons.

It looks like you are expected to walk the tree top-down from the given root (arg 2) until you hit the given node (arg 1), and then return the previously visited node.  If that's the assignment then so be it; but a much simpler approach would be:

father(Child, _, Parent) :- tree(Parent, Child, _) ; tree(Parent, _, Child).

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

Do not use those.  Really.

Thanks anyway for read this question.

HTH

-- 

---------------------------
|  BBB                b    \    Barbara at LivingHistory stop co stop uk
|  B  B   aa     rrr  b     |
|  BBB   a  a   r     bbb   |   ,008015L080180,022036,029037
|  B  B  a  a   r     b  b  |   ,047045,L014114L4.
|  BBB    aa a  r     bbb   |
-----------------------------

[Boris Vassilev]

Hello Juan,

for the second time I fall victim to [Cunningham's Law](https://meta.wikimedia.org/wiki/Cunningham%27s_Law).

This is because you are not providing all the context to the questions you ask :-(

I am guessing, having answered your previous email, that this is something you are doing in a course, and that the facts are something you were given, not something you came up with. You are probably going through the different ways to represent a tree data structure: before you had a tree as a compound term.

(BTW, still not sure what is the benefit of using nested lists instead of nested terms: why was your tree like this:

[[[], a, []], b, [[], c, []]]

instead of like this:

t(b, t(a, [], []), t(c, [], []))

But I digress.)

Now you are representing any number of binary trees as a "flattened" list of nodes (aka "Adjacency list"). I guess if you have a relational database, you would have a single table with four columns, one for the ID of the node, one for the value, and two columns for the IDs of the left and right child.

@Barbara: the ID is necessary if you have more than one tree or if the tree might have the same value in different nodes.

In the query you show, you are asking: "What is the value of the parent node of a node with a value 3, in the tree with root a4?"

You could google something like "relational database binary tree" or "binary tree adjacency list" and so on and read a bit on the subject, if your course material does not provide enough detail or good references.

The point is, again, there is not enough context, and both Barbara and me have to guess what exactly you are doing. Her solution is correct, if you knew that you have only one tree, and the values are unique.

Even in the case of "many trees in one table, node values not unique within a tree or in the table" you can start as she showed you, then go up the tree to check if you find the root you were given in the query. Or you could instead go down the tree starting at the given root, looking for the node with the ID you found.

In either case, since this boils down to finding a path in a graph, I am inclined to use an existing solution, as defined in this question:

https://stackoverflow.com/questions/30328433/definition-of-a-path-trail-walk

You only have to add definitions for the edges where the first two arguments are the nodes, as expected by the path meta-predicate. I will call them up/2 and down/2, depending which way you want to do it. So I saved the code from the link above in a file path.pl, and I now have this:

==
?- listing(tree).
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).

true.

?- listing(up).
up(B, A) :-
    tree(A, _, B, _).
up(B, A) :-
    tree(A, _, _, B).

true.

?- listing(down).
down(A, B) :-
    tree(A, _, B, _).
down(A, B) :-
    tree(A, _, _, B).

true.

?- [path].
true.

?- tree(X, 3, _, _),
   ( tree(X0, R, X, _) % as in Barbara's solution
   ; tree(X0, R, _, X)
   ),
   path(up, Path, X, a4). % a path up the tree to the root
X = c2,
X0 = b3,
R = 7,
Path = [c2, b3, a4] ;
false.

?- tree(X, 3, _, _),
   ( tree(X0, R, X, _) % as in Barbara's solution
   ; tree(X0, R, _, X)
   ),
   path(down, Path, a4, X). % a path down from the root
X = c2,
X0 = b3,
R = 7,
Path = [a4, b3, c2] ;
false.
==

The last two queries show you how you could search either up or down the tree.

Since you know that a binary tree is a directed, acyclic graph, you can get rid of some of the code in the definition of path. I will let you figure out what you can safely leave out.

Cheers,

Boris

Save our in-boxes! http://emailcharter.org

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+unsubscribe@googlegroups.com.
Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.