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.
My code is:
last_but_one(X, [X,_]).
last_but_one(X, [_|T]) :- last_but_one(X, T).
and the code they gave is:
last_but_one(X, [X,_]).
last_but_one(X, [_,Y|Ys]) :- last_but_one(X, [Y|Ys]).
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
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).
or even:
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]
; false.
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×
The reason for the big difference is that both f1 and f2 run purely determinate without any creation of a choicepoint.
Using
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))
).