2012-03-21 69 views
2

您如何在Prolog中編寫自己的謂詞,來完成nth1函數的功能?在SWI序言中實現nth1列表操作

對於那些不熟悉的功能,它的電源最好通過一個例子顯示:

- NTH1(2,[A,B,C],E,R)。

Ê= B

R = [A,C]

當NTH1函數被調用,並且通過了以下內容: - 的元素,其中的將被從取出的索引該列表(注意它不是零索引,並且在這裏,我們通過索引2) -列表(在這種情況下,它是[a,b,c]) -E,其將被分配給從列表中刪除的元素 - R,一個新列表,它將保存新列表,減去一個被刪除的元素。

我跺腳如何開始。任何意見,將不勝感激。我知道它應該可以在SWI-Prolog的大約3或4行中遞歸使用,我不知道從哪裏開始。

+0

標記爲功課,鑑於問題的性質和原來的海報的句柄(卡爾頓U) – 2012-03-21 17:24:18

回答

1

Check out this link這應該基本上給你答案。爲了讓你開始,請考慮你的基本情況,這應該是

nth1(1, [E|R], E, R). 

現在你怎麼能通過遞歸這個想法來寫其他情況?真的,這只是一個讓Prolog列表語法懸而未決的問題。

1

@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 
0

首先,將問題分解成更小的組成部分。從列表中選擇第N個項目很容易。收集差異不大。

因此,它分解爲兩個部分:

  • 首先,突發列表成前綴,所需的項目和後綴。

  • 接下來,通過append/3連接前綴和後綴以形成餘數列表。

my_nth1\4謂詞因此應該看起來像這樣:

nth1(N , List , Nth, Rest) :- 
    burst(N , List , Pfx , Nth , Sfx) , 
    append(Pfx , Sfx , Rest) 
    . 

% ------------------------------------------------------------------------------ 
% burst a list into 3 parts - a prefix, an item and a suffix 
% based on the specified offset N (where 0 indicates the first item of the list) 
% 
% The prefix is built up using a "difference list" as we recurse down looking 
% for the Nth item. 
% ------------------------------------------------------------------------------ 
burst(0 , [L|Ls] , []  , L , Ls ). 
burst(N , [L|Ls] , [L|Pfx] , Nth , Sfx) :- 
    N > 0 , 
    N1 is N - 1 , 
    burst(N1 , Ls , Pfx , Nth , Sfx) 
    .