边缘是由它的叶子组成的序列，从 左到右。 同边缘问题 [Hewitt & Patterson，1970] 包括确定两个二叉树是否具有相同的边缘。 例如，下面的前两棵树具有相同的边缘，但是 最后两个没有：
% . . .
% / \ / \ / \
% . 3 1 . 1 .
% / \ / \ / \
% 1 2 2 3 -2 3
example(1, fork(fork(leaf(1), leaf(2)), leaf(3))).
example(2, fork(leaf(1), fork(leaf(2), leaf(3)))).
example(3, fork(leaf(1), fork(leaf(-2), leaf(3)))).
一个简单的解决方案是将一棵树的叶子收集到一个列表中，然后
然后将它们与另一棵树的叶子进行比较。
/*
* SIMPLE SOLUTION
*/
sf_1(T1, T2) :-
walk(T1, [], Xs),
walk(T2, [], Xs).
walk(leaf(X), A, [X|A]).
walk(fork(L, R), A0, Xs) :-
walk(R, A0, A1),
walk(L, A1, Xs).
虽然简单，但这个解决方案被认为不优雅：首先，因为
当第一棵树非常大时，这可能是不切实际的；以及，第二，
因为当树的前几棵树不同时，效率非常低
树叶。因此，更好的解决方案是尽快停止比较
当发现第一个差异时，没有完全生成列表
包含第一棵树的边缘。
/*
* SUPPOSEDLY BETTER SOLUTION
*/
sf_2(T1, T2) :-
step([T1], [T2]).
step([], []).
step([T1|S1], [T2|S2]) :-
next(T1, S1, X, R1),
next(T2, S2, X, R2),
step(R1, R2).
next(leaf(X), S, X, S).
next(fork(L, R), S0, X, S) :-
next(L, [R|S0], X, S).
为了比较这两种解决方案的性能，我实现了一些谓词来运行自动化实验（通过使用 SWI-prolog，版本 9.0.4）：
/*
* EMPIRICAL COMPARISON
*/
comp(Case) :-
format('fsize sf-1 sf-2\n'),
forall( between(1, 10, I),
( N is 100000 * I,
tree(1, N, A),
( Case = true % trees with same fringes
-> tree(1, N, B)
; M is random(N//10), % trees with different fringes
flip(A, M, B) ),
time(10, sf_1(A, B), T1),
time(10, sf_2(A, B), T2),
format('~0e ~2f ~2f\n', [N, T1, T2]) ) ).
time(N, G, T) :-
garbage_collect,
S is cputime,
forall(between(1, N, _), ignore(call(G))),
T is (cputime - S) / N.
/*
* RANDOM TREE GENERATION AND MODIFICATION
*/
tree(X1, Xn, leaf(X1)) :-
X1 = Xn,
!.
tree(X1, Xn, fork(L, R)) :-
X1 < Xn,
random(X1, Xn, Xi),
Xj is Xi + 1,
tree(X1, Xi, L),
tree(Xj, Xn, R).
flip(leaf(X), Y, leaf(Z)) :-
( X = Y
-> Z is -X
; Z is X ).
flip(fork(L0, R0), X, fork(L, R)) :-
flip(L0, X, L),
flip(R0, X, R).
经验结果表明，当树木不具有相同的边缘时，第二个解决方案实际上比第一个解决方案更快：
?- comp(false).
fsize sf-1 sf-2
1e+05 0.01 0.00
2e+05 0.03 0.00
3e+05 0.05 0.00
4e+05 0.07 0.01
5e+05 0.09 0.01
6e+05 0.11 0.00
7e+05 0.12 0.01
8e+05 0.14 0.01
9e+05 0.17 0.00
1e+06 0.18 0.00
true.
但是，当树木确实具有相同的边缘时，第二个解决方案比第一个解决方案稍微慢：
?- comp(true).
fsize sf-1 sf-2
1e+05 0.02 0.03
2e+05 0.04 0.05
3e+05 0.06 0.08
4e+05 0.08 0.11
5e+05 0.10 0.12
6e+05 0.12 0.14
7e+05 0.12 0.16
8e+05 0.14 0.18
9e+05 0.17 0.19
1e+06 0.18 0.22
true.
问题：当边缘明显时，是否有可能实现一个比简单解决方案更快（通过常数因子，不一定是渐近更快）的解决方案（在Prolog中），但不是当条纹相同时速度变慢？换句话说，我们能否在没有开销的情况下实现高效的枚举？如果是的话，怎么办？
next/3目标才能始终获得更好或相同的运行时间。
sf_3(T1, T2) :-
stepping(T1, [T2],[]).
next(X, [T|Ts0],Ts) :-
t_next(T, X, Ts0,Ts).
t_next(leaf(X), X, Ts,Ts).
t_next(fork(L, R), X, Ts0,Ts) :-
t_next(L, X, [R|Ts0],Ts).
stepping(leaf(X), T2s0,T2s):-
next(X, T2s0,T2s).
stepping(fork(L, R), T2s0,T2s) :-
stepping(L, T2s0,T2s1),
stepping(R, T2s1,T2s).
T1中的节点信息已经可以用来使第二次转换更快失败（理想情况下，我们可以尽快失败，但
sf_1bsf_1b(T1, T2) :-
phrase(leaves(T1), Xs),
phrase(leaves(T2), Xs).
leaves(leaf(X)) -->
[X].
leaves(fork(L,R)) -->
leaves(L),
leaves(R).
?- sf_1(leaf(1),fork(leaf(2),_)).
loops, unexpected.
?- sf_1b(leaf(1),fork(leaf(2),_)).
false. % as expected
叶子），可以使用lazy_findall作为定界连续的替代品：
trees_equal(T1, T2) :-
lazy_findall(E, leaf_iter(T1, E), E1s),
lazy_findall(F, leaf_iter(T2, F), E2s),
lists_same(E1s, E2s).
leaf_iter(leaf(E), E).
leaf_iter(fork(L, R), E) :-
(leaf_iter(L, E) ; leaf_iter(R, E)).
lists_same([], []).
lists_same([H|T], [H|R]) :-
lists_same(T, R).
swi-prolog 中的结果：
?- trees_equal(fork(fork(leaf(1), leaf(2)), leaf(3)),
fork(leaf(1), fork(leaf(2), leaf(3)))).
% with pending residual goals
lazy_list(dummy, _),
lazy_list(dummy, _),
lazy_list(dummy, _) ;
false.
?- trees_equal(fork(fork(leaf(1), leaf(2)), leaf(3)),
fork(leaf(1), fork(leaf(-2), leaf(3)))).
false. % Fails as intended
?- trees_equal(leaf(1), fork(leaf(2), _)).
false. % Terminates as intended
?- trees_equal(fork(leaf(1),leaf(2)), fork(leaf(2),leaf(1))).
false. % Fails as intended