Prolog中的成員謂詞

Question

我想定義一個成員謂詞。成員（A，B）意味着列表A的所有成員都是列表B的成員。 top（N）定義A可以有多長。

這是我的嘗試：

top(5). 

members([X], L):- 
    member(X, L). 
members([X| Xs], L):- 
    member(X, L), 
    members(Xs, L), 
    length(Xs, M), 
    top(N), 
    M < N. 

我想用它如下：

members(L, [1,2,3]). 

我的執行的問題是，如果我;得到新的答案，我會完成一個錯誤：超出本地堆棧

?- members(I, [1,2,3]). 
I = [1] ; 
I = [2] ; 
I = [3] ; 
I = [1, 1] ; 
I = [1, 2] ; 
I = [1, 3] ; 
I = [1, 1, 1] ; 
I = [1, 1, 2] ; 
I = [1, 1, 3] ; 
I = [1, 1, 1, 1] ; 
I = [1, 1, 1, 2] ; 
I = [1, 1, 1, 3] ; 
I = [1, 1, 1, 1, 1] ; 
I = [1, 1, 1, 1, 2] ; 
I = [1, 1, 1, 1, 3] ; 
;ERROR: Out of local stack 

如何更改我的代碼以防止此內存不足？

Answer 1

如前所述，您的問題是您在之後做了長度檢查的遞歸調用，這意味着遞歸是無界的。不幸的是，剛剛動長度檢查這樣的遞歸調用上面...

members([X], L):- 
    member(X, L). 
members([X|Xs], L):- 
    length(Xs, M), 
    top(N), M < N, 
    member(X, L), 
    members(Xs, L). 

...不是那麼好，因爲我們得到這樣的：

L = [3, 1, 2, 3, 3] ; 
L = [3, 2, 2, 3, 3] ; 
L = [3, 3, 2, 3, 3] ; 
L = [3, 1, 3, 3, 3] ; 
L = [3, 2, 3, 3, 3] ; 
L = [3, 3, 3, 3, 3] ; 
ERROR: Out of global stack 

雖然這得到了我們答案，這是不是很有用，因爲它不會在斷裂後放入更大的謂詞中。它打破了，因爲我們只是進一步推動了這個問題。原因如下：

問題是，您是以自頂向下的方式構建列表。換句話說，我們定義如下的列表：List = [Head|Tail]其中我們規定Head和State的一些約束條件，Tail由相同約束定義的元素列表組成，並且由基本情形限定。這意味着，當我們處於遞歸調用的中間時，我們實際上只能訪問頭部 - 我們無法訪問尾部的內容，因爲只有在解釋器已經完成了向下並且到達基本案例（即members([X], L) :-），然後連續添加每個尾部到其頭部，直到構建最終列表。

它可能看起來像我們可以訪問的長度，因爲length/2調用坐在遞歸謂詞的中間，但是因爲列表中傳遞給length/2的變量在此階段不受任何約束，在計算長度之前，Prolog等待直到它完成了此點之下的遞歸調用。當然問題是長度檢查是遞歸的邊界，所以它會一直持續到內存不足。

雖然自頂向下遞歸往往是構建Prolog謂詞的默認方式，但正如本例所示，有時我們需要訪問我們正在創建的數據結構。解決方案是使用自下而上的遞歸。這是在Prolog中通過一個累加器謂詞實現的，該累加器謂詞從一個空列表開始，並通過遞歸謂詞傳遞累加器列表（它是一個完全基礎列表），逐個建立列表up。以下是我會寫一個累加器斷言對於這個問題：

members(I,L) :- 
    members_accumulator([],I,L). 

members_accumulator(Tail,I,L) :- 
    length(Tail, M), 
    top(N), 
    M < N, 
    member(X, L), 
    members_accumulator([X|Tail],I,L). 
members_accumulator(I,I,_). 

我們需要兩個謂詞，作爲第一個是圍繞通空單累加器謂詞蓄能器的包裝。基本情況不再與空列表有關 - 它只需要聲明最終的累加器列表實際上就是我們之後的最後一個列表（爲了這個目的，它已經通過了累加器謂詞） 。此外，在這種情況下，累加器謂詞需要按照此順序，否則會有一個選擇點在最後評估爲錯誤的權利。

在Prolog中獲取頭部遞歸，並且當您需要使用自下而上遞歸而不是自上而下時，這是一項不平凡的專長。直到我對The Art of Prolog進行了很好的閱讀之後，我才真正掌握了它。還應該有大量有關累積在線的信息。

Answer 2

您在遞歸之後檢查深度。所以遞歸的深度不受限制，只有結果列表被丟棄的時間太長。

Answer 3

這是一個不需要計算列表長度的替代實現。這裏的N是列表A的長度。這個解決方案給出了所有的答案，而不會退出堆棧。

members([X],L,1) :- member(X,L). 
members([H|T],L,N) :- N>1 , member(H,L) , N1 is N-1, members(T,L,N1). 

實例執行：

?- members(L,[1,2,3],5). 
L = [1, 1, 1, 1, 1] ; 
L = [1, 1, 1, 1, 2] ; 
L = [1, 1, 1, 1, 3] ; 
L = [1, 1, 1, 2, 1] ; 
... 
L = [3, 3, 3, 1, 2] ; 
L = [3, 3, 3, 3, 1] ; 
L = [3, 3, 3, 3, 2] ; 
L = [3, 3, 3, 3, 3] ; 
No 

Answer 4

使用meta-predicatemaplist/2， lambdas，和會員謂語memberd/2和簡單的寫：

:- use_module(library(lambda)). 

members(As,Bs,N) :- 
    length(Xs,N), 
    append(As,_,Xs), 
    maplist(Bs+\A^memberd(A,Bs), As). 

樣品查詢與縮寫答案序列：

?- members(As,[1,2,3],5). 
As = [   ] ; 
As = [  1] ; As = [  2] ;   As = [  3] ; 
As = [  1,1] ; As = [  1,2] ; /* ... */ As = [  3,3] ; 
As = [ 1,1,1] ; As = [ 1,1,2] ; /* ... */ As = [ 3,3,3] ; 
As = [ 1,1,1,1] ; As = [ 1,1,1,2] ; /* ... */ As = [ 3,3,3,3] ; 
As = [1,1,1,1,1] ; As = [1,1,1,1,2] ; /* ... */ As = [3,3,3,3,3] ; 
false. 

上面的查詢全局終止。 我們來看看解決方案集的大小：

 
?- setof(As,members(As,[1,2,3],5),Ass), length(Ass,N_Solutions). 
Ass   = [[],[1],[1,1],[1,1,1],[1,1,1|...],[1,1|...],[1|...],[...|...]|...], 
N_Solutions = 364. 

?- 364 =:= 1 + 3 + 3^2 + 3^3 + 3^4 + 3^5. 
true.