一个元素是否存在于列表的列表中？

Question

我想查找给定元素是否存在于列表列表中。如果元素存在于某处是列表的第一个列表，我只会变得真实。

有什么建议吗？

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

Answer 1

问题是 [[H|T1]|T2] 仅在给定 first 列表具有至少一个元素的情况下匹配。确实：例如 [[],[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).

第一个子句也使用下划线来指定我们在这些变量中是"not interested"。这对于 Prolog 程序很常见（可能解释器警告说 T1 和 T2 只被提到一次）。

因此，如果第一个列表已用完，我们只需移至下一个列表即可。

您的谓词做了很多 "packing" 和 "unpacking"。此外，我们可以使用 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

或者，您可能想使用 memberd/2 代替 member/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 提供的非常好的第二个解决方案的更紧凑版本（两个解决方案均为 s(0)）。实际上不需要像 member_lists_t/3 那样在谓词 member_lists/2 中使用具体化。事实上，在找到第一个解决方案后，使用 memberd_t/3 as first argument of 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 赋值时，此解决方案只会给出一个结果。通过更多的工作，可以将其更改为尾递归算法。但是这个问题似乎扩展到寻找一种方法来让这个 return 作为所有嵌入列表成员的单例元素集。

解决方案是将列表展平为单个列表，然后将列表变成一个集合。

从 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).

当然这并不完全令人满意，因为它不是尾递归并且效率不高。但是想出一个有效的尾递归解决方案会花费我几个小时，而且我还得修剪草坪。

一个元素是否存在于列表的列表中？

Does an element exists in a list of lists?

list

prolog

member