Reverse tree ratio

Question

I am trying to write a reversible relationship in a “clean” Prolog (no is , cut or similar stuff. Yes, this is homework), and I have to admit that I have no idea. I do not see any process for creating such a thing.

We are given the "uncertain" but reversible arithmetic relations (add, mult, equal, less, ...) that we must use to create these relations.

Now I'm trying to figure out how to create reversible functions by creating a tree(List,Tree) relation, which is true if List is a list of leaves of the binary Tree .

To achieve this, I am trying to create a tree_size(Tree,N) relation, which is true when Tree has N Here is my naive, irreversible attitude:

 tree_len(n(_,leaf,leaf),1). tree_len(n(op,G,D),N) :- tree_len(G,TG), tree_len(D,TD), add(TG,TD,N). 

I can execute the request tree_len(some tree, N) , but not, say, tree_len(X,3) , so it is not reversible. So far I have tried several things, but I must admit that I feel discouraged, because I do not know where and what to look for. Is there any way to do this?

Answer 1

Reason for no interruption

First, let's try to understand why your definition is not reversible. I will use failure-slice to better explain this. Therefore, consider the query tree_len(X,1). At first glance, everything is perfect, you will even get a good answer!

 ?- tree_len(T,1). T = n(_G267, leaf, leaf) 

But never ask for another answer, because it will loop:

 ?- tree_len(T,1). T = n(_G267, leaf, leaf) ; ** LOOPS ** 

So, the answer we got was a little distracted. At first glance, it looked as if everything was in order, and only on the retreat did the real problem arise. This is something to get used to in Prolog. Obviously your query using 3 was better selected. But it was luck.

There is an easy way to ensure this as a whole. Just add an additional false target to the request. Adding false means that we are no longer interested in any answers, since it can no longer be successful. Thus, all the distraction is removed, and we are directly faced with the problem:

 ?- tree_len(T,1), false. ** LOOPS ** 

So where does this cycle come from?

In clean, monotonous Prolog programs (such as this one), we can localize the cause without interruption by adding several false targets to our program. If the resulting program (called failure-slice ) does not exit, then the original program does not exit either. This is the minimum failure fragment for our request:

  ? - tree_len (T, 1), false .

 tree_len (n (_, leaf, leaf), 1): - false .
 tree_len (n (op, G, D), N): -
     tree_len (G, TG), false ,
     tree_len (D, TD) ,
     N is TG + TD .

There is a bit of our program left! It is this tiny fragment that is responsible for non-execution. If we want to fix the problem, we have to do something in this tiny part. Everything else is useless.

So, we need to somehow change the program so that this fragment no longer sings.

In fact, we have two options: we can use the successor of arithmetic or such as clpfd . The former is available on any Prolog system, the latter is provided only in some versions, such as SWI, YAP, SICStus, GNU, B.

Using successor-arithmetics

Now 3 is represented by s(s(s(0))) .

  tree_lensx (T, s (N)): -
    tree_lendiff (T, N, 0).

 tree_lendiff (n (_, leaf, leaf), N, N).
 tree_lendiff (n (op, G, D), s (N0), N): -
    tree_lendiff (G, N0, N1),
    tree_lendiff (D, N1, N).

I have used several common coding methods here.

Differences

The actual tree_lendiff/3 ratio, which is a natural number, is not one argument, but rather two. The actual number is the difference between the two. In this way, a reversible definition can be preserved.

Avoiding Left Recursion

Another method was to avoid left recursion. The length described by tree_lendiff/3 is actually equal to the length minus one. Remember that we have the first glitch? Here, too, will be the same failure-slice! However, by “shifting” the length by one, the head of the recursive rule now provides completion.

Using library(clpfd)

Initially, restrictions on finite domains for solving combinatorial problems were limited. But you can use them to obtain reversible arithmetic. Implementation in SWI and YAP even goes so far that it compiles into code, which is often equal to the performance of traditional irreversible (is)/2 , while still being reversible.

 :- use_module(library(clpfd)). tree_fdlen(n(_,leaf,leaf),1). tree_fdlen(n(op,G,D),N) :- N #= TG+TD, TG #>= 1, TD #>= 1, tree_fdlen(G,TG), tree_fdlen(D,TD). 

This program more closely matches your original definition. However, pay attention to the two goals TG #>= 1 and TD #>= 1 , which added redundant information to ensure the completion of this program.

Now we can list all trees of a certain range as follows:

 ?- Size in 0..4, tree_fdlen(T, Size). Size = 1, T = n(_A,leaf,leaf) ; Size = 2, T = n(op,n(_A,leaf,leaf),n(_B,leaf,leaf)) ; Size = 3, T = n(op,n(_A,leaf,leaf),n(op,n(_B,leaf,leaf),n(_C,leaf,leaf))) ; Size = 4, ... ; Size = 4, ... ; Size = 3, ... ; Size = 4, ... ; Size = 4, ... ; Size = 4, ... ; false. 

Pay attention to the exact order of the substitution of the answer! It doesn't just go 1,2,3,4! Rather, the answers are found in some order. It doesn’t matter which one, so far we are only interested in finding all the solutions!

Answer 2

An interesting problem.

Here is what I will do. Basically, your attitude is not reversible, since add / 3 is not. What I essentially did was replace the count by numbers with a count with lists of a size that matches the number of leaves - this is reversible (well, adding / 3 and length / 2 are reversible).

Is this something like what you need? The released code runs under YAP.

PS: it may not be the most concise solution, but it is out of my head. I will try to help if you have additional questions.

 :- use_module(library(lists)). do_tree_len(n(_,leaf,leaf), [X]). do_tree_len(n(op,G,D), [X1,X2|T]) :- append(TG, TD, [X1,X2|T]), TG \= [X1,X2|T], % To prevent infinite loops, when TG or TD is [] TD \= [X1,X2|T], do_tree_len(G, TG), do_tree_len(D, TD). tree_len(Tree, N):- length(L, N), do_tree_len(Tree, L).