23 replies to this topic

[Apprentice123]

How can I determine the height of a tree in prolog?

%X is a tree and Y height

height(X, Y)


height(nil,0). %Not element on tree


%Nl -> Node left || Nd -> Node right

height(tree(Nl, root, Nr), Y) :-  

%How do I check if Nl and Nr is nil to return Y=1

%How to go all the Nl and Nr to return the largest of them? 

[dbug]

I haven't used prolog for many years... hope this is correct...

First we need to define an empty tree. We will consider that nil is an empty tree of height 0. So we declare it:

height(nil, 0).

Now we need to create a recursive definition for height for the general case:

height(tree(L, _ , R), H) :- height(L, HL), height(R, HR), max(HL, HR, HN), H is HN + 1.

Eventually it will use the clause height(nil, 0), stopping the recursivity. This clause computes the height of both subtrees (L and R) into HL and HR, the max of them is stored in HN, and H is assigned the value of HN + 1.

Finally we have to define some clauses to compute max:

max(X, Y, X) :- X >= Y.

max(X, Y, Y) :- X < Y.

Now if we ask for the height of tree(tree(nil, 1, tree(nil, 2, nil)), 3, nil), we get:

?- height(tree(tree(nil, 1, tree(nil, 2, nil)), 3, nil), H).

H = 3

[Apprentice123]

dbug said:

I haven't used prolog for many years... hope this is correct...

First we need to define an empty tree. We will consider that nil is an empty tree of height 0. So we declare it:

height(nil, 0).

Now we need to create a recursive definition for height for the general case:

height(tree(L, _ , R), H) :- height(L, HL), height(R, HR), max(HL, HR, HN), H is HN + 1.

Eventually it will use the clause height(nil, 0), stopping the recursivity. This clause computes the height of both subtrees (L and R) into HL and HR, the max of them is stored in HN, and H is assigned the value of HN + 1.

Finally we have to define some clauses to compute max:

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

Now if we ask for the height of tree(tree(nil, 1, tree(nil, 2, nil)), 3, nil), we get:

?- height(tree(tree(nil, 1, tree(nil, 2, nil)), 3, nil), H).
H = 3

I try to compile and I get the following errors:

ERROR: Undefined procedure: height/4
ERROR:     However, there are definitions for:
ERROR:         height/2
false.

Why do I get these errors?

I have to assign a variable to a tree? For example:
X = tree(tree(nil, 1, tree(nil, 2, nil)), 3, nil).
height(X, H).

[dbug]

You can do that, but it's not necessary. It's very strange, there isn't any height definition with four arguments in any of the clauses I wrote. Did you start with a clean set of clauses and the program only contains what I wrote (there should be only four lines in the program) ?

[Apprentice123]

dbug said:

You can do that, but it's not necessary. It's very strange, there isn't any height definition with four arguments in any of the clauses I wrote. Did you start with a clean set of clauses and the program only contains what I wrote (there should be only four lines in the program) ?

I did so:

height(nil,0).


height(tree(Se,Raiz,Sd), A) :- height(Se, Ae), height(Sd, Ad),

                            maior(Ae, Ad, CONT), A is CONT + 1.

                          

maior(X, Y, X):- X >= Y.

maior(X, Y, Y):- X < Y.

The error is:

ERROR: toplevel: Undefined procedure: height/2 (DWIM could not correct goal)

[dbug]

The error says that you are referencing something called "altura". It is not present in the code you posted so you must have something hidden somewhere that adds more definitions (or you are asking an incorrect question. Maybe you are asking "altura(tree, H)" instead of "height(tree, H)" ?)

[Apprentice123]

dbug said:

The error says that you are referencing something called "altura". It is not present in the code you posted so you must have something hidden somewhere that adds more definitions (or you are asking an incorrect question. Maybe you are asking "altura(tree, H)" instead of "height(tree, H)" ?)

Sorry, I got the post. The error is

ERROR: toplevel: Undefined procedure: height/2 (DWIM could not correct goal)

[dbug]

height/2 is clearly defined in the program... it makes no sense...

What compiler are you using ? what do you do to load the program and make the query ?

What I did was:

• Save the program (the 4 clauses) to a file called tree.pl
  
• Run a new instance of the compiler
  
• Load the program with: [tree].
  
• Ask the question with: height(..., H).

[Apprentice123]

dbug said:

height/2 is clearly defined in the program... it makes no sense...

What compiler are you using ? what do you do to load the program and make the query ?

What I did was:

• Save the program (the 4 clauses) to a file called tree.pl
  
• Run a new instance of the compiler
  
• Load the program with: [tree].
  
• Ask the question with: height(..., H).

Thank you... I was calling the wrong program (['height.pl']. but the name is tree.pl :w00t: )

I do not understand how this sentence determines the maximum height between HR and HL

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

[dbug]

Prolog is basically a backtracker. It tries to find a match between your question and the rules you have defined. If a match is found it replies "true" (or what values are needed to satisfy the asked question).

If you ask max(1, 2, 3). it will return false because there are only two rules for max and both require that the third argument must be equal to the first one or second one. If some of the arguments of the question are not specified (variable names are used), then Prolog tries to find all possible values for that variables than can be derived from the defined rules. This can be seen as a return value in procedural programming. The third argument to max can be seen as the result of the operation that we are looking for.

For example, if we ask max(1, 2, R). Prolog will try to find a value for R that satisfies the rules defined. A rule has two parts separated by ':-'. Rules can be read like this: if the right part of the rule is true then the left part is assumed to be true.

In our case, we can try to apply the first rule: max(X, Y, X) :- X >= Y. We have specified the first and second arguments, so Prolog knows that X = 1 and Y = 2. But max(X, Y, X) can only be true if X >= Y is true. In this case this is false. We must apply the second rule: max(X, Y, Y) :- X < Y. Prolog knows that X = 1 and Y = 2. In this case X < Y is satisfied so the left part of the rule is valid. This means that max(1, 2, 2) is valid (substituting known variables into the rule). The last step is to find a match between our asked question and this true fact. max(1, 2, R) must match max(1, 2, 2). The only possibility to do this is that R = 2. This is exactly what Prolog says for our request.

We could also ask max(X, 1, 2). and he will answer X = 2. There are no input and output arguments in Prolog. It only tries to find matchings between questions made and rules available.

[Apprentice123]

dbug said:

Prolog is basically a backtracker. It tries to find a match between your question and the rules you have defined. If a match is found it replies "true" (or what values are needed to satisfy the asked question).

If you ask max(1, 2, 3). it will return false because there are only two rules for max and both require that the third argument must be equal to the first one or second one. If some of the arguments of the question are not specified (variable names are used), then Prolog tries to find all possible values for that variables than can be derived from the defined rules. This can be seen as a return value in procedural programming. The third argument to max can be seen as the result of the operation that we are looking for.

For example, if we ask max(1, 2, R). Prolog will try to find a value for R that satisfies the rules defined. A rule has two parts separated by ':-'. Rules can be read like this: if the right part of the rule is true then the left part is assumed to be true.

In our case, we can try to apply the first rule: max(X, Y, X) :- X >= Y. We have specified the first and second arguments, so Prolog knows that X = 1 and Y = 2. But max(X, Y, X) can only be true if X >= Y is true. In this case this is false. We must apply the second rule: max(X, Y, Y) :- X < Y. Prolog knows that X = 1 and Y = 2. In this case X < Y is satisfied so the left part of the rule is valid. This means that max(1, 2, 2) is valid (substituting known variables into the rule). The last step is to find a match between our asked question and this true fact. max(1, 2, R) must match max(1, 2, 2). The only possibility to do this is that R = 2. This is exactly what Prolog says for our request.

We could also ask max(X, 1, 2). and he will answer X = 2. There are no input and output arguments in Prolog. It only tries to find matchings between questions made and rules available.

Thank you very much.
I have to replace an element in a tree, using Prolog?

I think:
a -> element to be replaced
b -> new element
X -> tree
How can I traverse the tree to find the element to be replaced?

element(A, B, X)

[dbug]

Prolog is a language to ask questions, not to manipulate data structures. I don't think you could do a replacement in a node of a tree...