@EMS答案相當不錯,但正確實施謂詞可能會非常棘手。我們必須考慮每個實例化模式,這對於關係nth1/4是有意義的,導致該問題需要正好相同的內建行爲。所以nth1也可以搜索元素和插入的位置。
SWI-Prolog用於在不同實現之間進行效率切換,但應該可以在需要時測試實例的關係進行建模。
而不是nth1我把它叫做mth1。
mth1(1, [X|R], X, R).
mth1(_, L, _, _) :-
L == [], % (==)/2 fails when L is a var
!, fail.
mth1(P, [H|T], X, [H|R]) :-
( var(P) % are we searching the position?
-> mth1(Q, T, X, R),
P is Q + 1
; Q is P - 1,
mth1(Q, T, X, R)
).
測試L == []
需要插入。
當然調試它是強制性的,這裏的一些簡單的測試:
?- mth1(2,[a,b,c,d,e],X,Y).
X = b,
Y = [a, c, d, e] ;
false.
?- mth1(X,[a,b,c,d,e],b,Y).
X = 2,
Y = [a, c, d, e] ;
false.
?- mth1(2,X,b,[a,c,d,e]).
X = [a, b, c, d, e] ;
false.
您應該檢查是否通過SWI-Prolog的允許的所有實例化圖案覆蓋...
如何執行這種簡單的思想實現?這裏的基本測試
test_performance(N) :-
numlist(1, N, L),
time(test_performance(L, N, nth1)),
time(test_performance(L, N, mth1)).
test_performance(L, N, P) :-
writeln(P),
writeln('access last'),
time((call(P, N, L, X, _), assertion(X == N))),
writeln('find position of last'),
time((call(P, Z, L, N, _), assertion(Z == N))),
writeln('add tail'),
time(call(P, N, _, tail, L)).
令我驚訝的是,偷看元素,並在尾部增加是(略)快,而找到的位置是方法要慢(因爲思念尾遞歸?):
?- test_performance(1000000).
nth1
access last
% 1,000,011 inferences, 0,624 CPU in 0,626 seconds (100% CPU, 1602617 Lips)
find position of last
% 1,000,003 inferences, 0,670 CPU in 0,671 seconds (100% CPU, 1493572 Lips)
add tail
% 1,000,009 inferences, 0,482 CPU in 0,484 seconds (100% CPU, 2073495 Lips)
% 3,000,243 inferences, 1,777 CPU in 1,781 seconds (100% CPU, 1688815 Lips)
mth1
access last
% 1,000,002 inferences, 0,562 CPU in 0,563 seconds (100% CPU, 1779702 Lips)
find position of last
% 2,000,001 inferences, 1,998 CPU in 2,003 seconds (100% CPU, 1001119 Lips)
add tail
% 1,000,000 inferences, 0,459 CPU in 0,460 seconds (100% CPU, 2179175 Lips)
% 4,000,223 inferences, 3,019 CPU in 3,027 seconds (100% CPU, 1324901 Lips)
true .
事實上,與較長的列表位置搜索顯示了其效率低下,採用了經典的StackOverflow:
?- test_performance(2000000).
nth1
access last
% 2,000,011 inferences, 1,218 CPU in 1,221 seconds (100% CPU, 1641399 Lips)
find position of last
% 2,000,003 inferences, 1,327 CPU in 1,330 seconds (100% CPU, 1507572 Lips)
add tail
% 2,000,009 inferences, 0,958 CPU in 0,960 seconds (100% CPU, 2088038 Lips)
% 6,000,243 inferences, 3,504 CPU in 3,511 seconds (100% CPU, 1712549 Lips)
mth1
access last
% 2,000,002 inferences, 1,116 CPU in 1,118 seconds (100% CPU, 1792625 Lips)
find position of last
% 1,973,658 inferences, 2,479 CPU in 2,485 seconds (100% CPU, 796219 Lips)
% 3,973,811 inferences, 3,595 CPU in 3,603 seconds (100% CPU, 1105378 Lips)
ERROR: Out of local stack
標記爲功課,鑑於問題的性質和原來的海報的句柄(卡爾頓U) – 2012-03-21 17:24:18