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

Question

我想查找一个给定元素是否存在于一个列表的列表中。如果该元素仅存在于列表的第一个列表中，那么我只会得到true。

有什么建议吗？

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

- Alator

---

member(Xs, Xss), member(X, Xs) - false

Answer 1

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.

这个版本已经好多了，但仍然不能去除所有冗余的答案。

为了解决这个问题并消除所有这样的多余项，我们设置了奖励。

- false

Answer 2

这个怎么样？

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

- user27815

---

绝对是一种纯粹、良好的解决方案。但是真的有必要先转换整个列表吗？这并不是一个明确的要求。 - false

Python是一种高级编程语言，它被广泛用于数据科学、人工智能、Web开发等领域。它具有简单易学、代码可读性强、拥有丰富的第三方库等优点。许多大型公司和组织都在使用Python来构建他们的应用程序和服务。 - false

这里有一个情况，你的解决方案不会终止，但人们甚至可以期望它能够确定性地成功：memberlists(X,[[X|_]|_])。将其与 memberd(X,[X|_]) 进行比较，后者也会成功并终止。 - false

Answer 3

这是@user27815提供的非常好的第二种解决方案的更紧凑版本（两个解决方案都使用s(0)）。实际上，在成员列表/2谓词中不需要像在member_lists_t/3中执行reification。事实上，只需将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

正在以确定性方式终止。

- tas

---

显然是最好的解决方案。但是，这个答案看起来非常简单，却非常低效，这不是有点奇怪吗？也许应该提出进一步的问题和悬赏。 - false

@false：是的，这确实很奇怪。Richard O'Keefe在《Prolog编程艺术》的引言中写道，该书的主题之一是“优雅不是可选的”。我觉得这是一个非常准确的观察。然而，这似乎是一个反例。至少根据他对该语句的第一种解释（效率）来看是如此。然而，就可维护性而言（第二种解释），它仍然适用：在你的帖子中，我可以一眼看出正在发生什么。在我的帖子中...好吧，如果我不熟悉具象化... - tas

至少你的解决方案真的很纯粹和高效！也许一些高阶元谓词可以覆盖这个抽象... - false

Answer 4

使用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).

- user27815

---

member_lists_t/3 不要使用 _t。 - false

请参考SICStus|SWI中的library(reif)。 - false

member_lists/2 中不需要具体化！ - false

目前对于 member_lists(a,[[b,c]]) 成功。 - false

and member_lists_t - user27815

Answer 5

问题在于[[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).

- Willem Van Onsem

---

有点错过了。你好 :) - Alator

仍然太复杂。 - false

@false，你能提供一些不那么复杂的东西吗？ - Alator

@Alator：请看我的回答。 - false

Answer 6

这是我的方法，使用 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...)

- coder

---

memberlists(X,[[a]|Xs]), Xs = [_|_] 的执行结果错误，应该是成功的（或者循环执行）。 - false

对于 memberlists(X,[[a,A]]), A = a. 这个问题，已经得到了两个答案。因此仍然存在冗余解。 - false

@false，使用memberd/2解决的问题，请查看更新后的答案，欢迎任何建议！ - coder

memberlists(X,[[X|_]|_]) 可以确定性地成功。 - false

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代码如下：

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

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

- DavidD

---

谓词memberlist(X,L)应该只在L是一个列表且X是L中某个元素的成员时才为真。因此，memberlist(X,[a]).应该失败，但您的实现没有。 - lambda.xy.x

顺便提一下，a可能被描述为不充分指定，但对于memberlist(X,[[]]).也是适用的：空列表中包含无内容，但实现声称空列表包含空列表。 - lambda.xy.x