Most general query only finding one solution for each number of leaves of tree N in Exercize 3.5 from Learn Prolog Now

Question

So check the exercize 3.5 description here:

%%  Exercise  3.5 %%

%  Binary trees are trees where all internal nodes have exactly two children. 
%  The smallest binary trees consist of only one leaf node. We will represent leaf nodes as 
%  leaf(Label) . For instance, leaf(3) and leaf(7) are leaf nodes, and therefore small binary 
%  trees. Given two binary trees B1 and B2 we can combine them into one binary tree using the 
%  functor tree/2 as follows: tree(B1,B2) . So, from the leaves leaf(1) and leaf(2) we can build
%  the binary tree tree(leaf(1),leaf(2)) . And from the binary trees tree(leaf(1),leaf(2)) and 
%  leaf(4) we can build the binary tree tree(tree(leaf(1),  leaf(2)),leaf(4)).

% Now, define a predicate swap/2 , which produces the mirror image of the binary tree that is its first argument. For example:

%    ?-  swap(tree(tree(leaf(1),  leaf(2)),  leaf(4)),T).
%    T  =  tree(leaf(4),  tree(leaf(2),  leaf(1))).
%    yes

And this is my implementation:

swap(tree(leaf(X), leaf(Y)), tree(leaf(Y), leaf(X))).
swap(tree(B1, leaf(Y)), tree(leaf(Y), SwapB1)) :- 
    dif(B1, leaf(_)),
    swap(B1, SwapB1).
swap(tree(leaf(X), B2), tree(SwapB2, leaf(X))) :- 
    dif(B2, leaf(_)),
    swap(B2, SwapB2).
swap(tree(B1, B2), tree(B2,B1)) :- 
    dif(B1, leaf(_)),
    dif(B2, leaf(_)).

When I execute the following query swap(T1,T). I get:

?- swap(T1,T).
T1 = tree(leaf(_A), leaf(_B)),
T = tree(leaf(_B), leaf(_A)) ;
T1 = tree(tree(leaf(_A), leaf(_B)), leaf(_C)),
T = tree(leaf(_C), tree(leaf(_B), leaf(_A))) ;
T1 = tree(tree(tree(leaf(_A), leaf(_B)), leaf(_C)), leaf(_D)),
T = tree(leaf(_D), tree(leaf(_C), tree(leaf(_B), leaf(_A)))) ;
T1 = tree(tree(tree(tree(leaf(_A), leaf(_B)), leaf(_C)), leaf(_D)), leaf(_E)),
T = tree(leaf(_E), tree(leaf(_D), tree(leaf(_C), tree(leaf(_B), leaf(_A))))) .

As you can see Prolog is not considering all of the solutions for each number of leaves N. For example, for N = 4, the case T1 = tree( tree(leaf(_A) , leaf(_B)), tree(leaf(_C), leaf(_D)) ) is not being considered.

Edit: changed the case N=3 to N=4, now i think it's more clear.

I'm trying to make Prolog consider all solutions for each number of leaves N of the tree without relying on CLPFD as suggested before by user @false

Thank you for your attention!

Note that this is an unusual tree. More useful binary trees have a value at each node and empty leafs, for example `tree(a, tree(b, empty, empty), tree(c, empty, empty))`. — TA_intern, Oct 25 '21 at 06:10

Isabelle Newbie · Accepted Answer · 2021-10-24T23:01:32.090

Your problem is called fairness of enumeration. Prolog's backtracking algorithm explores the last recursive call in a goal as deeply as possible, so if you have two recursive calls in a goal, enumeration will always get "stuck" in the second one.

Here's a simpler example, just enumerating trees:

tree(leaf(_)).
tree(tree(Left, Right)) :-
    tree(Left),
    tree(Right).

Just like in your case, this builds trees that deepen to the right:

?- tree(Tree).
Tree = leaf(_1986) ;
Tree = tree(leaf(_1992), leaf(_1996)) ;
Tree = tree(leaf(_1992), tree(leaf(_2002), leaf(_2006))) ;
Tree = tree(leaf(_1992), tree(leaf(_2002), tree(leaf(_2012), leaf(_2016)))) ;
Tree = tree(leaf(_1992), tree(leaf(_2002), tree(leaf(_2012), tree(leaf(_2022), leaf(_2026))))) .

The fix for this is to introduce some kind of "size" measure, like the number of leaves, and to enumerate guided by the size. This is why using CLPFD arithmetic was suggested. Without arithmetic, one way of doing this is with lists.

Here is a predicate that relates trees and lists of their leaves:

tree_leaves(leaf(X), [X]).
tree_leaves(tree(Left, Right), Leaves) :-
    LeftLeaves = [_ | _],
    RightLeaves = [_ | _],
    append(LeftLeaves, RightLeaves, Leaves),
    tree_leaves(Left, LeftLeaves),
    tree_leaves(Right, RightLeaves).

For example:

?- Leaves = [a, b, c], tree_leaves(Tree, Leaves).
Leaves = [a, b, c],
Tree = tree(leaf(a), tree(leaf(b), leaf(c))) ;
Leaves = [a, b, c],
Tree = tree(tree(leaf(a), leaf(b)), leaf(c)) ;
false.

As you can see, for a fixed-length list, this did enumerate all (two) possible tree structures.

So now we want to do something similar with a fair enumeration of all fixed-length lists -- this will force a fair enumeration of the corresponding trees. Lists can be enumerated fairly with the length/2 predicate:

?- length(List, N).
List = [],
N = 0 ;
List = [_2242],
N = 1 ;
List = [_2242, _2248],
N = 2 ;
List = [_2242, _2248, _2254],
N = 3 ;
List = [_2242, _2248, _2254, _2260],
N = 4 .

Therefore:

?- length(Leaves, N), tree_leaves(Tree, Leaves).
Leaves = [_2798],
N = 1,
Tree = leaf(_2798) ;
Leaves = [_2798, _2804],
N = 2,
Tree = tree(leaf(_2798), leaf(_2804)) ;
Leaves = [_2798, _2804, _2810],
N = 3,
Tree = tree(leaf(_2798), tree(leaf(_2804), leaf(_2810))) ;
Leaves = [_2798, _2804, _2810],
N = 3,
Tree = tree(tree(leaf(_2798), leaf(_2804)), leaf(_2810)) ;
Leaves = [_2798, _2804, _2810, _2816],
N = 4,
Tree = tree(leaf(_2798), tree(leaf(_2804), tree(leaf(_2810), leaf(_2816)))) ;
Leaves = [_2798, _2804, _2810, _2816],
N = 4,
Tree = tree(leaf(_2798), tree(tree(leaf(_2804), leaf(_2810)), leaf(_2816))) ;
Leaves = [_2798, _2804, _2810, _2816],
N = 4,
Tree = tree(tree(leaf(_2798), leaf(_2804)), tree(leaf(_2810), leaf(_2816))) ;
Leaves = [_2798, _2804, _2810, _2816],
N = 4,
Tree = tree(tree(leaf(_2798), tree(leaf(_2804), leaf(_2810))), leaf(_2816)) ;
Leaves = [_2798, _2804, _2810, _2816],
N = 4,
Tree = tree(tree(tree(leaf(_2798), leaf(_2804)), leaf(_2810)), leaf(_2816)) ;
Leaves = [_2798, _2804, _2810, _2816, _2822],
N = 5,
Tree = tree(leaf(_2798), tree(leaf(_2804), tree(leaf(_2810), tree(leaf(_2816), leaf(_2822))))) .

We can package this up:

fairtree(Tree) :-
    length(Leaves, _N),
    tree_leaves(Tree, Leaves).

And then test your swap/2 predicate with fair enumeration:

?- fairtree(Tree), swap(Tree, Swapped).
Tree = tree(leaf(_2122), leaf(_2128)),
Swapped = tree(leaf(_2128), leaf(_2122)) ;
Tree = tree(leaf(_2874), leaf(_2878)),
Swapped = tree(leaf(_2878), leaf(_2874)),
dif(_2906, _2874),
dif(_2918, _2878) ;
Tree = tree(leaf(_2122), tree(leaf(_2128), leaf(_2134))),
Swapped = tree(tree(leaf(_2134), leaf(_2128)), leaf(_2122)) ;
Tree = tree(leaf(_2922), tree(leaf(_2932), leaf(_2936))),
Swapped = tree(tree(leaf(_2936), leaf(_2932)), leaf(_2922)),
dif(_2974, _2932),
dif(_2986, _2936) ;
Tree = tree(leaf(_2690), tree(leaf(_2700), leaf(_2704))),
Swapped = tree(tree(leaf(_2700), leaf(_2704)), leaf(_2690)),
dif(_2732, _2690) ;
Tree = tree(tree(leaf(_2122), leaf(_2128)), leaf(_2134)),
Swapped = tree(leaf(_2134), tree(leaf(_2128), leaf(_2122))) ;
Tree = tree(tree(leaf(_2934), leaf(_2938)), leaf(_2942)),
Swapped = tree(leaf(_2942), tree(leaf(_2938), leaf(_2934))),
dif(_2980, _2934),
dif(_2992, _2938) ;
Tree = tree(tree(leaf(_2702), leaf(_2706)), leaf(_2710)),
Swapped = tree(leaf(_2710), tree(leaf(_2702), leaf(_2706))),
dif(_2738, _2710) ;
Tree = tree(leaf(_2122), tree(leaf(_2128), tree(leaf(_2134), leaf(_2140)))),
Swapped = tree(tree(tree(leaf(_2140), leaf(_2134)), leaf(_2128)), leaf(_2122)) ;
Tree = tree(leaf(_2970), tree(leaf(_2980), tree(leaf(_2990), leaf(_2994)))),
Swapped = tree(tree(tree(leaf(_2994), leaf(_2990)), leaf(_2980)), leaf(_2970)),
dif(_3042, _2990),
dif(_3054, _2994) ;
Tree = tree(leaf(_2738), tree(leaf(_2748), tree(leaf(_2758), leaf(_2762)))),
Swapped = tree(tree(tree(leaf(_2758), leaf(_2762)), leaf(_2748)), leaf(_2738)),
dif(_2800, _2748) ;
Tree = tree(leaf(_2724), tree(leaf(_2734), tree(leaf(_2744), leaf(_2748)))),
Swapped = tree(tree(leaf(_2734), tree(leaf(_2744), leaf(_2748))), leaf(_2724)),
dif(_2776, _2724) .

(For whatever it's worth, the canonical definition of swap is much shorter and simpler than yours. Two clauses are enough.)

Very elegant answer, thank you very much! May I ask you where could I take a look at the canonical version of `swap`? Also, fairness of enumeration is a new concept to me! Mind if I ask where I can further study this topic? I'm currently on Chapter 3 of Learn Prolog Now! and I wonder if this topic is covered later in the book? Thank you for your information! — Luiz, Oct 24 '21 at 23:50
I'm happy to show you the canonical `swap`, but you might want to give it another try first :-) Ask yourself if there are trees that your current implementation doesn't handle. Or even better, ask your current implementation! `?- tree(Tree), \+ swap(Tree, Swapped).` This should lead you to a case you don't currently handle, which should lead you to simplifications you can make. — Isabelle Newbie, Oct 25 '21 at 03:14
As for fairness, I'm fairly sure I learned the term from @false. I just checked the indices of a handful of Prolog books, and I didn't see it listed in any of them. If you search here on StackOverflow, you'll find a few more mentions of the concept and examples of it. Not sure how much other material there is. — Isabelle Newbie, Oct 25 '21 at 03:16
[Fair enumeration](https://www.google.com/search?q=%22fair+enumeration%22) seems to be bit more prominent in FP. As for Prolog books, which of them mentions "iterative deepening"? — false, Oct 25 '21 at 18:51
`tree_leaves(tree(leaf(1),leaf(2)),[3|_]).` loops. Failure expected. — false, Oct 25 '21 at 18:55
That is: It seems there is no beginners' book that uses one or the other notion. — false, Oct 25 '21 at 18:59
@false wow, so I just tested a failure slice after and before `append/3` in `tree_leaves/2` from @Isabelle Newbie and that's what's causing the infinite loop in the query `tree_leaves(tree(leaf(1),leaf(2)),[3|_]).`! I don't know why, but it must be because the lists LeftLeaves and RightLeaves are being infinitely generated by Prolog, since they haven't been instantiated yet. To fix that, just put append/3 at the end of the recursive case of `tree_leaves/2`, so Prolog will have instantiated lists to work with, limitting the solution range to one(or no) solution. — Luiz, Oct 26 '21 at 18:58
@Luiz: With your suggested fix, `tree_leaves(T, [1,2])` does not terminate. See my answer for the correct and Prolog way to solve this. — false, Oct 26 '21 at 20:21

false · Answer 2 · 2022-08-11T10:14:04.287

Bad usage of dif/2

First some remarks on the goal dif(B1, leaf(_)). With this you intend to express that it should only be true if B1 is not a leaf. But what you said is that B1 should be different to a very particular leaf structure whose argument does not occur anywhere else. In other words, there is no term for B1 that makes this goal fail.

(Both Scryer and SWI have here a bug with the anonymous variable. So let's use _A instead.)

?- B1 = leaf(2), dif(B1, leaf(_A)).
   B1 = leaf(2), dif:dif(leaf(2),leaf(_A)).

That is certainly not what you intend. What you meant was that this dif should be true for all _A. Or otherwise, that the functor of B1 must be different to leaf/1. There is no common way to express this idiomatically. But in your case, just consider which trees are not leaves! Certainly, they must look like tree(_,_). So you can replace that goal and all others by B1 = tree(_,_).

Mirroring a tree

Then for your definition of swap/2: It fails for swap(leaf(1),T). That might give you a clue. In general it is very often an error to try to specialize a program into too many separate cases. Instead, try to keep it as simple as possible. For that take the definition of a tree as a starting template, and fill in the remainder:

is_tree(leaf(_)).
is_tree(tree(L, R)) :-
   is_tree(L),
   is_tree(R).

% Version 0, too general w.r.t. the second argument, but otherwise fine
swap_v0(leaf(_), _).
swap_v0(tree(L,R), _) :-
   swap_v0(L, _),
   swap_v0(R, _).

Counterexample:

?- swap_v0(leaf(_), anything).
   true.     % unexpected

Evidently, this definition is too general, this anything is pointless. So we need to specialize the program. Let's do this very slowly:

swap_v1(leaf(E), leaf(E)).
swap_v1(tree(L,R), tree(_,_)) :-
   swap_v1(L, _),
   swap_v1(R, _).

Still too general, I will leave the rest to you.

Enumerating infinite answers/solutions

Prolog is very good at enumerating one infinite set that is described with infinitely many answers:

?- length(L, N).
   L = [], N = 0
;  L = [_A], N = 1
;  L = [_A,_B], N = 2
;  L = [_A,_B,_C], N = 3
;  L = [_A,_B,_C,_D], N = 4
;  L = [_A,_B,_C,_D,_E], N = 5
;  ... .

It is only because of the finite space limit here on SO that we cannot have the entire sequence of answers. (Just kidding, it's because we have finite machines, always the cheap ones.) But just tell me a number and I will tell you were this number will appear. That's essentially what a fair enumeration is about.

But now consider that we want to have one further list:

?- length(L, N), length(K, M).
   L = [], N = 0, K = [], M = 0
;  L = [], N = 0, K = [_A], M = 1
;  L = [], N = 0, K = [_A,_B], M = 2
;  L = [], N = 0, K = [_A,_B,_C], M = 3
;  L = [], N = 0, K = [_A,_B,_C,_D], M = 4
;  L = [], N = 0, K = [_A,_B,_C,_D,_E], M = 5
;  ... .

So here we have two infinite sets but only one is enumerated in a fair manner. That is the problem with chronological backtracking. We need to reformulate such queries in such a manner that only a single infinite sequence of answers will be produced.

Same problem with enumerating is_tree/2. Except that here it is a bit more confusing if you attempt to follow Prolog's execution step-by-step. Don't try it, yes there are tracers out there, but you will not understand this with the help of them. Instead, try to find some size-like norm such that for each such size, Prolog will enumerate all corresponding trees with finitely many answers. Like the number of leaves. Or, even better the list of all leaves. That is, for each such list, Prolog will enumerate all corresponding trees. Here is such a definition:

tree_leaves(T, Es) :-
   Es = [_|Ls],
   phrase(tree(T, Ls,[]), Es).

tree(leaf(E), Ls,Ls) --> [E].
tree(tree(L,R), [_|Ls0],Ls) -->
   tree(L, Ls0,Ls1),
   tree(R, Ls1,Ls).

Now all trees can be enumerated like so:

?- length(Es, N), tree_leaves(T, Es).
   Es = [_A], N = 1, T = leaf(_A)
;  Es = [_A,_B], N = 2, T = tree(leaf(_A),leaf(_B))
;  Es = [_A,_B,_C], N = 3, T = tree(leaf(_A),tree(leaf(_B),leaf(_C)))
;  Es = [_A,_B,_C], N = 3, T =  tree(tree(leaf(_A),leaf(_B)),leaf(_C))
;  Es = [_A,_B,_C,_D], N = 4, T =  tree(leaf(_A),tree(leaf(_B),tree(leaf(_C),leaf(_D))))
;  Es = [_A,_B,_C,_D], N = 4, T = tree(leaf(_A),tree(tree(leaf(_B),leaf(_C)),leaf(_D)))
;  Es = [_A,_B,_C,_D], N = 4, T = tree(tree(leaf(_A),leaf(_B)),tree(leaf(_C),leaf(_D)))
;  Es = [_A,_B,_C,_D], N = 4, T = tree(tree(leaf(_A),tree(leaf(_B),leaf(_C))),leaf(_D))
;  Es = [_A,_B,_C,_D], N = 4, T = tree(tree(tree(leaf(_A),leaf(_B)),leaf(_C)),leaf(_D))
;  Es = [_A,_B,_C,_D,_E], N = 5, T = tree(leaf(_A),tree(leaf(_B),tree(leaf(_C),tree(leaf(_D),leaf(_E)))))
;  ... .

Test your code

With tree_leaves/2 you can now also test your definition of swap/2! The following must never succeed

?- any(Es), tree_leaves(T, Es), reverse(Es, EsR),
   \+ ( swap(T, TS),
        tree_leaves(TS, EsS),
        EsS == EsR
   ).

To be honest, I'm having a hard time trying to understand the `phrase/2` and `any/1` predicates. I tried reading `phrase/2`'s documentation but to no avail and I couldn't find `any/1` in the documentation. Although I did understand what you meant by dividing the query in too many cases and the fair enumeration explanation with lists was really helpful. — Luiz, Oct 27 '21 at 18:15
For `any/1` take any (pure) predicate. Like `any([_,_,_]).` or whatever. Otherwise you ignored [my suggestion](https://stackoverflow.com/questions/69623834/tree-methods-going-on-infinite-loop/69634058#comment123100258_69634058) to start with successor arithmetics which would be the adequate way to proceed. `phrase/2` belongs to [tag:dcg]s, that is a further step but needed to solve `tree_leaves/2` in a satisfactory manner. — false, Oct 28 '21 at 09:29

Most general query only finding one solution for each number of leaves of tree N in Exercize 3.5 from Learn Prolog Now

2 Answers2

Bad usage of dif/2

Mirroring a tree

Enumerating infinite answers/solutions

Test your code