这个问题是要在一个列表中找到倒数第二个字符，例如：
?- last_but_one(X, [a,b,c,d]).
X = c.
我的代码是：
last_but_one(X, [X,_]).
last_but_one(X, [_|T]) :- last_but_one(X, T).
他们给出的代码是：
last_but_one(X, [X,_]).
last_but_one(X, [_,Y|Ys]) :- last_but_one(X, [Y|Ys]).
last_but_one(X, [_|T]) :- last_but_one(X, T).
^^^^^^^^^^
provided X is the lbo-element in T
^^ then, it follows, that (that's an arrow!)
^^^^^^^^^^^^^^^^^^^^^^
X is also the lbo-element of T with one more element
换句话说：如果你已经在给定列表 T 中有一个 lbo 元素，那么你可以构建新的列表，在前面添加任何其他具有相同 lbo 元素的元素。
关于效率，人们可能会争论哪个版本更好。如果你真的很在意这个，最好选择：
last_but_one_f1(E, Es) :-
Es = [_,_|Xs],
xs_es_lbo(Xs, Es, E).
xs_es_lbo([], [E|_], E).
xs_es_lbo([_|Xs], [_|Es], E) :-
xs_es_lbo(Xs, Es, E).
last_but_one_f2(E, [F,G|Es]) :-
es_f_g(Es, F, G, E).
es_f_g([], E, _, E).
es_f_g([G|Es], _, F, E) :-
es_f_g(Es, F, G, E).
永远不要忘记普通测试：
?- last_but_one(X, Es).
Es = [X,_A]
; Es = [_A,X,_B]
; Es = [_A,_B,X,_C]
; Es = [_A,_B,_C,X,_D]
; Es = [_A,_B,_C,_D,X,_E]
; Es = [_A,_B,_C,_D,_E,X,_F]
; false.
以下是我旧笔记本电脑的一些基准测试结果：
SICStus SWI
4.3.2 7.3.20-1
--------------+----------+--------
you 0.850s | 3.616s | 4.25×
they 0.900s | 16.481s | 18.31×
f1 0.160s | 1.625s | 10.16×
f2 0.090s | 1.449s | 16.10×
mat 0.880s | 4.390s | 4.99×
dcg 3.670s | 7.896s | 2.15×
dcgx 1.000s | 7.885s | 7.89×
ap 1.200s | 4.669s | 3.89×
这种差异的原因在于f1和f2都是纯确定性运行，没有创建任何选择点。
使用：
bench_last :-
\+ ( length(Ls, 10000000),
member(M, [you,they,f1,f2,mat,dcg,dcgx,ap]), write(M), write(' '),
atom_concat(last_but_one_,M,P), \+ time(call(P,L,Ls))
).
这里有另一种使用DCGs的方法。我认为这个解决方案更具“图形化”特点，但在SICStus中似乎相当慢：
last_but_one_dcg(L, Ls) :-
phrase( ( ..., [L,_] ), Ls).
... --> [].
... --> [_], ... .
我们描述了一个列表必须具备什么样的特征才能拥有倒数第二个元素。它看起来像这样：在前面是任何内容(...)，然后在末尾是两个元素。
通过扩展phrase/2，速度会变快一些。请注意，扩展本身不再是符合规范的程序。
last_but_one_dcgx(L, Ls) :-
...(Ls, Ls2),
Ls2 = [L,_].
last_but_one(X,[b])。 你会发现它们都给出了相同的答案（false），但第二个解决方案需要更少的步骤，因为它在进行递归调用之前返回false。last_but_one(X) --> [X,_].
last_but_one(X) -->
[_],
last_but_one(X).
last_but_one(L, Ls) :-
phrase(last_but_one(L), Ls).
我们有三个版本进行比较：
last_but_one//1last_but_one_you/2last_but_one_they/2测试案例包括查找一个包含一千万个元素的列表的倒数第二个元素。
我们有：
这段文字展示了一个性能测试的结果。在这个测试中，创建一个长度为10,000,000的列表，并分别使用三种函数来找到该列表中倒数第二个元素。其中，第一种函数的名字是“last_but_one”，第二种函数的名字是“last_but_one_you”，第三种函数的名字是“last_but_one_they”。测试结果显示，第一种函数不仅易于阅读，而且执行速度是最快的，第二种函数的执行速度略慢，第三种函数的执行速度则远远落后于前两者。因此，作者建议始终以优雅和易读为首要目标，通常情况下，这也能够获得更好的性能。last_but_one_append(X,Es) :-
append(_, [X,_], Es).
:- use_module(library(lists)).
last_but_one_reverse(X, Es) :-
reverse(Es, [_,X|_]).
last_but_one_rev(X, Es) :-
rev(Es, [_,X|_]). % (SICStus only)
或者，我们可以使用纯自制的myappend/3和myreverse/2：
myappend([], Bs, Bs).
myappend([A|As], Bs, [A|Cs]) :-
myappend(As, Bs, Cs).
last_but_one_myappend(X, Es) :-
myappend(_, [X,_], Es).
myreverse(Es, Fs) :-
same_length(Es, Fs), % for universal termination in mode (-,+)
myreverse_(Es, Fs, []).
myreverse_([], Fs, Fs).
myreverse_([E|Es], Fs, Fs0) :-
myreverse_(Es, Fs, [E|Fs0]).
last_but_one_myreverse(X, Es) :-
myreverse(Es, [_,X|_]).
我们来运行实验1吧！
bench_last :-
\+ ( length(Ls, 10000000),
member(M, [you,they,f1,f2,mat,dcg,dcgx,ap,
append,reverse,rev,
myappend,myreverse]),
write(M), write(' '),
atom_concat(last_but_one_,M,P),
\+ time(call(P,_L,Ls))
).
SICStus | SICStus | SWI |
4.3.2 | 4.3.3 | 7.3.20 |
-------------------+---------+--------|
you 0.26秒 | 0.10秒 | 0.83秒 | 3.1× 8.3×
they 0.27秒 | 0.12秒 | 1.03秒 | 3.8× 8.5×
f1 0.04秒 | 0.02秒 | 0.43秒 | 10.8× 21.5×
f2 0.02秒 | 0.02秒 | 0.37秒 | 18.5× 18.5×
mat 0.26秒 | 0.11秒 | 1.02秒 | 3.9× 9.0×
dcg 1.06秒 | 0.77秒 | 1.47秒 | 1.3× 1.9×
dcgx 0.31秒 | 0.17秒 | 0.97秒 | 3.1× 5.7×
ap 0.23秒 | 0.11秒 | 0.42秒 | 1.8× 3.8×
append 1.50秒 | 1.13秒 | 1.57秒 | 1.0× 1.3×
reverse 0.36秒 | 0.32秒 | 1.02秒 | 2.8× 3.1×
rev 0.04秒 | 0.04秒 | --"-- | 25.6× 25.6×
myappend 0.48秒 | 0.33秒 | 1.56秒 | 3.2× 4.7×
myreverse 0.27秒 | 0.26秒 | 1.11秒 | 4.1× 4.2×
非常令人印象深刻！在SICStus/SWI加速列中，差异>10%的部分被加粗。
注1：本答案中显示的所有测量值均基于IntelHaswell处理器Core i7-4700MQ。
注2：SICStus提供了rev/2，但SWI没有。我们比较最快的“反转”库谓词。
注3：SWI命令行选项-G1G是必需的，以防止全局堆栈溢出错误。
注4：此外，尝试使用SWI命令行选项-O（优化），但没有产生任何改进。
另一种解决方案：
代码:
last_but_one(R,[X|Rest]):-
( Rest=[_], R=X
; last_but_one(R,Rest)
).
| ?- last_but_one(Elem,List).
List = [Elem,_A] ? ;
List = [_A,Elem,_B] ? ;
List = [_A,_B,Elem,_C] ? ;
List = [_A,_B,_C,Elem,_D] ? ;
List = [_A,_B,_C,_D,Elem,_E] ? ;
List = [_A,_B,_C,_D,_E,Elem,_F] ? ;
List = [_A,_B,_C,_D,_E,_F,Elem,_G] ? ;
List = [_A,_B,_C,_D,_E,_F,_G,Elem,_H] ?
yes
last_but_one(Elem, List) 只会产生一个答案，而不是无限多个。你定义中的 -> 负责这一点。 - falseap）。 - false
last_but_one(X, [_,Y,Z|T]) :- last_but_ont(X, [Y,Z|T]).它强制第二个参数是至少有3个元素的列表，使约束更加精确。 :) - lurkerlast_but_one(X, [X,_]).所以再添加一个匹配第二个参数为两个元素列表的子句是多余的。 - lurker