列表中是否存在元素？

Question

我想查找給定的元素是否存在於列表列表中。如果元素存在於某個列表的第一個列表中，我只會變爲true。

有什麼建議嗎？

memberlist(X,[[X|T1]|T2]). 
memberlist(X,[[H|T1]|T2]) :- 
    memberlist(X,[T1|T2]). 

Answer 1

的問題是，僅[[H|T1]|T2]匹配給出的第一列表具有至少一種元素。確實：[[],[1,4],[2,5]]例如不是與[[H|T1]|T2]相統一。

所以，你可以通過添加一個條款，解決這個問題：

memberlist(X,[[]|T2]) :- 
    memberlist(X,T2). 

由此獲得：

memberlist(X,[[X|_]|_]). 
memberlist(X,[[H|T1]|T2]) :- 
    memberlist(X,[T1|T2]). 
memberlist(X,[[]|T2]) :- 
    memberlist(X,T2). 

第一條也使用下劃線來指定，我們是在「不感興趣」這些變量。這在Prolog程序中很常見（可能翻譯人員警告說T1和T2僅提及一次）。

因此，如果第一個列表已用盡，我們只需移動到下一個列表。

你的謂詞做了很多「打包」和「解包」。此外，我們可以使用內建的member/2。因此，我們可以把它改寫：

memberlist(X,[H|_]) :- 
    member(X,H). 
memberlist(X,[_|T2]) :- 
    memberlist(X,T2). 

Answer 2

memberlists(X, Xss) :- 
    member(Xs, Xss), 
    member(X, Xs). 

類似member/2，這將產生許多冗餘的答案，如：

?- memberlists(X, [[a,a],[a],[a]]). 
    X = a 
; X = a % redundant 
; X = a % redundant 
; X = a. % redundant 

或者，你可能要代替member/2使用memberd/2。

memberlists2(X, Xss) :- 
    memberd(Xs, Xss), 
    memberd(X, Xs). 

?- memberlists2(X, [[a,a],[a],[a]]). 
    X = a 
; X = a % redundant 
; false. 

這樣好多了，但仍不能刪除所有多餘的答案。

對於一個解決方案，刪除所有這樣的冗餘已設置賞金。

Answer 3

這裏是我的方法使用sort/2和flat/2是扁平的列表只有一層：

memberlists(X, Xss) :- Xss = [_|_], 
         flat(Xss, FL), 
         sort(FL, OutL), 
         memberd(X, OutL). 

memberd(X, [X|_Xs]). 
memberd(X, [Y|Xs]) :- 
    dif(X,Y), 
    memberd(X, Xs).      

flat([],[]). 
flat([H|T],R) :- H = [_|_], flat(T,T1), append(H,T1,R). 

測試用例：

?- memberlists(X,[[a,A]]), A = a. 
X = A, A = a ; 
false. 

?- memberlists(X,[[a]|Xs]), Xs = [_|_]. 
Xs = [[X]] ; 
X = a, 
Xs = [[_G13004]], 
dif(a, _G13004) ; 
Xs = [[X, _G12784]] . 

?- memberlists(X,[[a,a],[Y],[b]]). 
X = Y ; 
X = a, 
dif(a, Y) ; 
X = b, 
dif(b, Y) ; 
false. 

?- memberlists(X,[[a,a],[a],[a]]). 
X = a ; 
false. 

?- memberlists(X,[[[a,a],[a],[a]]]). 
X = [a] ; 
X = [a, a] ; 
false. 

?- memberlists(X,[L]). 
L = [X] ; 
L = [X, _G12710] ; 
L = [_G12923, X], 
dif(X, _G12923) ; 
L = [X, _G12710, _G12716] ; 
L = [_G12935, X, _G12941], 
dif(X, _G12935) . (and goes on...) 

?- memberlists(X,L). 
L = [[X]] 
L = [[X, _G12704]] ; 
L = [[_G12920, X]], 
dif(X, _G12920) ; 
L = [[X, _G12704, _G12710]] ; 
L = [[_G12932, X, _G12938]], 
dif(X, _G12932) ; 
L = [[_G13018, _G13021, X]], 
dif(X, _G13021), 
dif(X, _G13018) ; 
L = [[X, _G12704, _G12710, _G12716]] . (and goes on...) 

Answer 4

這個是什麼？

list([])  --> []. 
list([L|Ls]) --> [L], list(Ls). 

concatenation([]) --> []. 
concatenation([List|Lists]) --> 
    list(List), 
    concatenation(Lists). 

memberd(X, [X|_Xs]). 
memberd(X, [Y|Xs]) :- 
    dif(X,Y), 
    memberd(X, Xs). 

memberlists(X, Lists):- 
    phrase(concatenation(Lists),List), 
    memberd(X,List). 

Answer 5

隨着if_/3：

memberd_t(_,[],false). 
memberd_t(X,[Y|Ys],Truth) :- 
if_(X=Y, Truth=true, memberd_t(X,Ys,Truth)). 

member_lists_t(_,[],false). 
member_lists_t(X,[H|T],Truth):- 
if_(memberd_t(X,H),Truth=true,member_lists_t(X,T,Truth)). 

member_lists(X,Lists):- 
member_lists_t(X,Lists,true). 

Answer 6

下面是@ user27815更緊湊版本的非常好的解決方案第2的（S（0），這兩種解決方案）。實際上，不需要像member_lists_t/3那樣在謂詞member_lists/2中使用實例。事實上，使用memberd_t/3作爲if_/3的第一個參數足以在找到第一個解決方案後終止。因此，關係可以表述爲，象這樣一個目標一個規則：

member_lists(X,[H|T]) :- 
    if_(memberd_t(X,H),true,member_lists(X,T)). 

查詢

?- member_lists(X,[[a,a],[a]]). 
X = a ? ; 
no 

只生產單一的解決方案。查詢

?- member_lists(X,[[X|_]|_]). 

true 

確定性地終止。

Answer 7

答案原來的問題如下：

memberlist(X, [X| _]) :- !. 
memberlist(X, [[A|B]|_]) :- 
    memberlist(X,[A|B]), !. 
memberlist(X, [_ | Rest]) :- 
    memberlist(X, Rest). 

該解決方案將只給一個結果，當X被賦予在查詢中值。通過多一點工作，可以將其更改爲尾遞歸算法。但是這個問題似乎擴展到尋找一種方法來讓這個返回的所有嵌入式列表的成員單身元素。

解決方法是將列表平鋪到單個列表中，然後將列表轉換爲集合。

從cs.uni-potsdam.de弄平的代碼是：

flatten(List, Flat) :- 
    flatten(List, Flat, []). 

flatten([], Res, Res) :- !. 
flatten([Head|Tail], Res, Cont) :- 
     !, 
     flatten(Head, Res, Cont1), 
     flatten(Tail, Cont1, Cont). 
flatten(Term, [Term|Cont], Cont). 

用於車削的列表（從http://www.cs.oswego.edu/~odendahl/coursework/notes/prolog/synopsis/）

member(X,[X|_]). 
member(X,[_|Y]) :- member(X,Y). 

make_set([],[]). 
make_set(X,Y) :- setof(Z,member(Z,X),Y). 

所以最後一塊是設置的代碼：

setofmembers(NestedLists, Set) :- 
    flatten(NestedLists,Flat), 
    make_set(Flat,Set). 

memberlist2(X,Lists) :- 
    setofmembers(Lists,Set), 
    member(X,Set). 

當然這並不完全令人滿意，因爲它不是尾遞歸，它不是v有效率。但想出一個高效的尾部遞歸解決方案將需要幾個小時，我必須修剪草坪。