边缘是由它的叶子组成的序列，从 左到右。 相同的边缘问题 [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中），并且不是当条纹相同时，速度会变慢？怎么办？
sf_3(T1, T2) :-
stepping(T1, [T2],[]).
next(X, [T2|T2s0],T2s) :-
t_next(T2, X, T2s0,T2s).
t_next(leaf(X), X, T2s,T2s).
t_next(fork(L, R), X, T2s0,T2s) :-
t_next(L, X, [R|T2s0],T2s). % [R|_] could be eliminated for R a leaf/1.
stepping(leaf(X), T2s0,T22):-
next(X, T2s0,T2s).
stepping(fork(L, R), T2s0,T2s) :-
stepping(L, T2s0,T2s1),
stepping(R, T2s1,T2s).