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