大多数一般查询仅在 Learn Prolog Now 的练习 3.5 中为树 N 的每个叶子数找到一个解决方案
Most general query only finding one solution for each number of leaves of tree N in Exercize 3.5 from Learn Prolog Now
所以在这里查看练习 3.5 的描述：
%% 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
这是我的实现：
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(_)).
当我执行以下查询时 swap(T1,T). 我得到：
?- 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))))) .
如您所见，Prolog 并未考虑每个叶数 N 的所有解决方案。例如，对于 N = 4，情况 T1 = tree( tree(leaf(_A) , leaf(_B)), tree(leaf(_C), leaf(_D)) ) 未被考虑。
编辑：将 N=3 的情况更改为 N=4，现在我觉得更清楚了。
我试图让 Prolog 考虑树的每个叶子数 N 的所有解决方案，而不依赖于用户@false
之前建议的 CLPFD
感谢您的关注！
你的问题叫做枚举公平。 Prolog 的回溯算法尽可能深入地探索目标中的最后一个递归调用，因此如果您在一个目标中有 两个 递归调用，枚举将始终“卡在”第二个中。
这是一个更简单的例子，只是枚举树：
tree(leaf(_)).
tree(tree(Left, Right)) :-
tree(Left),
tree(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))))) .
解决这个问题的方法是引入某种“大小”度量，例如叶子的数量，并根据大小进行枚举。这就是建议使用 CLPFD 算法的原因。如果没有算术，一种方法是使用列表。
这是一个关联树及其叶子列表的谓词：
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).
例如：
?- 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.
如您所见，对于固定长度的列表，这确实枚举了所有（两个）可能的树结构。
所以现在我们想要对所有固定长度列表的公平枚举做类似的事情——这将强制对相应的树进行公平枚举。可以使用 length/2 谓词公平地枚举列表：
?- 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 .
因此：
?- 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))))) .
我们可以打包：
fairtree(Tree) :-
length(Leaves, _N),
tree_leaves(Tree, Leaves).
然后用公平枚举测试你的 swap/2 谓词：
?- 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) .
（无论如何，swap 的规范定义比你的更短更简单。两个子句就足够了。）
dif/2
的错误用法
首先是关于目标的一些评论 dif(B1, leaf(_))。有了这个，你打算表达只有当 B1 不是叶子时它才应该是真的。但是你说的是 B1 应该不同于一个非常特殊的叶结构，它的参数不会出现在其他任何地方。换句话说，B1 没有使这个目标失败的术语。
（Scryer 和 SWI 在这里都有一个 bug 和匿名变量。所以我们用 _A 代替。）
?- B1 = leaf(2), dif(B1, leaf(_A)).
B1 = leaf(2), dif:dif(leaf(2),leaf(_A)).
那肯定不是你想要的。你的意思是这个 dif 应该对所有 _A 都是正确的。或者，B1 的函子必须不同于 leaf/1。没有通用的方式来惯用地表达这一点。但就您而言，只需考虑哪些树不是叶子！当然，它们必须看起来像 tree(_,_)。因此，您可以用 B1 = tree(_,_).
替换该目标和所有其他目标
镜像一棵树
那么对于 swap/2 的定义：swap(leaf(1),T) 失败。这可能会给你一个线索。一般来说，尝试将程序专门化为太多不同的情况通常是错误的。相反，尽量保持简单。为此，以树的定义作为起始模板，并填写余数：
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, _).
反例：
?- swap_v0(leaf(_), anything).
true. % unexpected
显然这个定义太笼统了，这个anything毫无意义。所以我们需要专业化程序。让我们慢慢来：
swap_v1(leaf(E), leaf(E)).
swap_v1(tree(L,R), tree(_,_)) :-
swap_v1(L, _),
swap_v1(R, _).
还是太笼统了，剩下的就交给你了
枚举无限answers/solutions
Prolog 非常擅长枚举一个用无限多个答案描述的无限集合：
?- 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
; ...
只是由于 SO 的有限 space 限制，我们无法获得完整的答案序列。 （开个玩笑，因为我们的机器有限，而且总是便宜的。）但只要告诉我一个数字，我就会告诉你这个数字是否会出现。这就是公平枚举的本质。
但现在考虑我们想要再列出一个列表：
?- 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
; ...
所以这里我们有两个无限集合，但只有一个以公平的方式被枚举。这就是按时间顺序回溯的问题。我们需要以仅生成一个无限序列的答案的方式重新表述此类查询。
与枚举 is_tree/2 相同的问题。不同之处在于，如果您试图一步步地跟随 Prolog 的执行，那么这里会更加令人困惑。不要尝试，是的，那里有示踪剂，但你不会在他们的帮助下理解这一点。相反，尝试找到一些类似大小的范数，这样对于每个这样的大小，Prolog 将枚举所有具有有限多个答案的对应树。就像叶子的数量。或者，更好的是所有叶子的列表。也就是说，对于每个这样的列表，Prolog 将枚举所有对应的树。下面是这样一个定义：
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).
现在所有树都可以像这样枚举了：
?- 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)))))
; ...
测试你的代码
有了 tree_leaves/2，您现在还可以测试 swap/2 的定义！以下绝不能成功
?- any(Es), tree_leaves(T, Es), reverse(Es, EsR),
\+ ( swap(T, TS),
tree_leaves(TS, EsS),
EsS == EsR
).
所以在这里查看练习 3.5 的描述：
%% 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
这是我的实现：
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(_)).
当我执行以下查询时 swap(T1,T). 我得到：
?- 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))))) .
如您所见，Prolog 并未考虑每个叶数 N 的所有解决方案。例如，对于 N = 4，情况 T1 = tree( tree(leaf(_A) , leaf(_B)), tree(leaf(_C), leaf(_D)) ) 未被考虑。
编辑：将 N=3 的情况更改为 N=4，现在我觉得更清楚了。
我试图让 Prolog 考虑树的每个叶子数 N 的所有解决方案，而不依赖于用户@false
之前建议的 CLPFD感谢您的关注！
你的问题叫做枚举公平。 Prolog 的回溯算法尽可能深入地探索目标中的最后一个递归调用，因此如果您在一个目标中有 两个 递归调用，枚举将始终“卡在”第二个中。
这是一个更简单的例子，只是枚举树：
tree(leaf(_)).
tree(tree(Left, Right)) :-
tree(Left),
tree(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))))) .
解决这个问题的方法是引入某种“大小”度量，例如叶子的数量，并根据大小进行枚举。这就是建议使用 CLPFD 算法的原因。如果没有算术，一种方法是使用列表。
这是一个关联树及其叶子列表的谓词：
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).
例如：
?- 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.
如您所见，对于固定长度的列表，这确实枚举了所有（两个）可能的树结构。
所以现在我们想要对所有固定长度列表的公平枚举做类似的事情——这将强制对相应的树进行公平枚举。可以使用 length/2 谓词公平地枚举列表：
?- 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 .
因此：
?- 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))))) .
我们可以打包：
fairtree(Tree) :-
length(Leaves, _N),
tree_leaves(Tree, Leaves).
然后用公平枚举测试你的 swap/2 谓词：
?- 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) .
（无论如何，swap 的规范定义比你的更短更简单。两个子句就足够了。）
dif/2
的错误用法首先是关于目标的一些评论 dif(B1, leaf(_))。有了这个，你打算表达只有当 B1 不是叶子时它才应该是真的。但是你说的是 B1 应该不同于一个非常特殊的叶结构，它的参数不会出现在其他任何地方。换句话说，B1 没有使这个目标失败的术语。
（Scryer 和 SWI 在这里都有一个 bug 和匿名变量。所以我们用 _A 代替。）
?- B1 = leaf(2), dif(B1, leaf(_A)).
B1 = leaf(2), dif:dif(leaf(2),leaf(_A)).
那肯定不是你想要的。你的意思是这个 dif 应该对所有 _A 都是正确的。或者，B1 的函子必须不同于 leaf/1。没有通用的方式来惯用地表达这一点。但就您而言，只需考虑哪些树不是叶子！当然，它们必须看起来像 tree(_,_)。因此，您可以用 B1 = tree(_,_).
镜像一棵树
那么对于 swap/2 的定义：swap(leaf(1),T) 失败。这可能会给你一个线索。一般来说，尝试将程序专门化为太多不同的情况通常是错误的。相反，尽量保持简单。为此，以树的定义作为起始模板，并填写余数：
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, _).
反例：
?- swap_v0(leaf(_), anything).
true. % unexpected
显然这个定义太笼统了，这个anything毫无意义。所以我们需要专业化程序。让我们慢慢来：
swap_v1(leaf(E), leaf(E)).
swap_v1(tree(L,R), tree(_,_)) :-
swap_v1(L, _),
swap_v1(R, _).
还是太笼统了，剩下的就交给你了
枚举无限answers/solutions
Prolog 非常擅长枚举一个用无限多个答案描述的无限集合：
?- 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
; ...
只是由于 SO 的有限 space 限制，我们无法获得完整的答案序列。 （开个玩笑，因为我们的机器有限，而且总是便宜的。）但只要告诉我一个数字，我就会告诉你这个数字是否会出现。这就是公平枚举的本质。
但现在考虑我们想要再列出一个列表：
?- 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
; ...
所以这里我们有两个无限集合，但只有一个以公平的方式被枚举。这就是按时间顺序回溯的问题。我们需要以仅生成一个无限序列的答案的方式重新表述此类查询。
与枚举 is_tree/2 相同的问题。不同之处在于，如果您试图一步步地跟随 Prolog 的执行，那么这里会更加令人困惑。不要尝试，是的，那里有示踪剂，但你不会在他们的帮助下理解这一点。相反，尝试找到一些类似大小的范数，这样对于每个这样的大小，Prolog 将枚举所有具有有限多个答案的对应树。就像叶子的数量。或者，更好的是所有叶子的列表。也就是说，对于每个这样的列表，Prolog 将枚举所有对应的树。下面是这样一个定义：
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).
现在所有树都可以像这样枚举了：
?- 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)))))
; ...
测试你的代码
有了 tree_leaves/2，您现在还可以测试 swap/2 的定义！以下绝不能成功
?- any(Es), tree_leaves(T, Es), reverse(Es, EsR),
\+ ( swap(T, TS),
tree_leaves(TS, EsS),
EsS == EsR
).