列表中的序言递归，最后一个元素 [英] Prolog Recursion in lists, last but one element

问题描述

问题是找到列表中的最后一个字符，例如

The question is to find the last but one character in a list, e.g.

?- 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]).

当我学习 Haskell 时，我记得当对某些列表中的第 2 个、第 3 个或第 n 个字符提出问题时，其结构与提供的答案相同，所以我知道按照它们的方式编写它我写了它有一定的意义.但我似乎仍然按照我写的方式得到了正确的答案.

When I was studying Haskell, I can recall that when questions asked for the 2nd, 3rd, or nth character in some list, the structure was the same as the answer that's been supplied, so I know writing it the way they've written it has some significance. But I still seem to get correct answers with the way I have written it.

是我写错了吗?做出答案的人写的代码更好吗?如果是，怎么写?

Is the way I have written it wrong? Is the code that the guys who made the answer wrote better—and if so, how?

推荐答案

您的原始版本更易于阅读.特别是，递归规则读取 - 从右到左读取

Your original version is much simpler to read. In particular, the recursive rule reads - reading it right-to-left

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 元素.

In other words: If you have already an lbo-element in a given list T, then you can construct new lists with any further elements in front that also have the very same lbo-element.

人们可能会争论哪个版本在效率方面更可取.如果您真的对此感兴趣，请选择:

One might debate which version is preferable as to efficiency. If you are really into that, rather take:

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

永远不要忘记一般测试:

Never forget general testing:

| ?- 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] ? ...

这里是我的旧实验室的一些基准:

And here are some benchmarks on my olde labtop:

          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 都是纯粹确定的，没有创建任何选择点.

The reason for the big difference is that both f1 and f2 run purely determinate without any creation of a choicepoint.

使用

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

这篇关于列表中的序言递归，最后一个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！