我想查找一个给定元素是否存在于一个列表的列表中。如果该元素仅存在于列表的第一个列表中,那么我只会得到true。
有什么建议吗?
memberlist(X,[[X|T1]|T2]).
memberlist(X,[[H|T1]|T2]) :-
memberlist(X,[T1|T2]).
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.
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).
memberlists(X,[[X|_]|_])
。将其与 memberd(X,[X|_])
进行比较,后者也会成功并终止。 - false这是@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
正在以确定性方式终止。
使用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).
[[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).
这是我的方法,使用 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...)
memberlists(X,[[a]|Xs]), Xs = [_|_]
的执行结果错误,应该是成功的(或者循环执行)。 - falsememberlists(X,[[a,A]]), A = a.
这个问题,已经得到了两个答案。因此仍然存在冗余解。 - falsememberlists(X,[[X|_]|_])
可以确定性地成功。 - false对于原始问题的答案如下:
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).
当然,这并不是完全令人满意的,因为它不是尾递归且不太有效。但是想出一个高效的尾递归解决方案需要我花费几个小时,而我还得修剪草坪。
memberlist(X,L)
应该只在L
是一个列表且X
是L
中某个元素的成员时才为真。因此,memberlist(X,[a]).
应该失败,但您的实现没有。 - lambda.xy.xa
可能被描述为不充分指定,但对于memberlist(X,[[]]).
也是适用的:空列表中包含无内容,但实现声称空列表包含空列表。 - lambda.xy.x
member(Xs, Xss), member(X, Xs)
- false