我想查找给定的元素是否存在于列表列表中。如果元素存在于某个列表的第一个列表中,我只会变为true。列表中是否存在元素?
有什么建议吗?
memberlist(X,[[X|T1]|T2]).
memberlist(X,[[H|T1]|T2]) :-
memberlist(X,[T1|T2]).
我想查找给定的元素是否存在于列表列表中。如果元素存在于某个列表的第一个列表中,我只会变为true。列表中是否存在元素?
有什么建议吗?
memberlist(X,[[X|T1]|T2]).
memberlist(X,[[H|T1]|T2]) :-
memberlist(X,[T1|T2]).
的问题是,仅[[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).
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.
这样好多了,但仍不能删除所有多余的答案。
对于一个解决方案,删除所有这样的冗余已设置赏金。
这里是我的方法使用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...)
这个是什么?
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).
随着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更紧凑版本的非常好的解决方案第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
确定性地终止。
显然是最好的解决方案。然而,[这个答案](http://stackoverflow.com/a/43426864/772868)看起来非常简单 - 但它效率很低,这不是有点奇怪吗?也许这应该进一步的问题和赏金。 – false
@ false:是的,确实很奇怪。 Richard O'Keefe在“Prolog的工艺”一书的前言中写道,其中一本书的主题是“优雅不是可选的”。我发现这是一个非常准确的观察。但这似乎是一个反例。至少根据他对声明的第一种解释(效率)。但是,就可维护性而言(第二种解释)它仍然适用:在您的文章中,我可以首先看到发生了什么。在我的...好吧,如果我不熟悉物化...... – tas
至少你的解决方案真的很纯粹和高效!也许某些更高级的[tag:meta-predicate]可能包含抽象... – false
答案原来的问题如下:
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有效率。但想出一个高效的尾部递归解决方案将需要几个小时,我必须修剪草坪。
如果'''L'''是谓语'''memberlist(X,L)'''应该是正确的一个列表和'''X'''是''''L'''的一个元素的成员。因此'''memberlist(X,[a])。'''应该会失败,但是你的实现不会。 –
顺便说一句'''a'''可能被覆盖为未指定,但它也适用于'''memberlist(X,[[]])。'':空列表的列表不包含任何内容,但实现声明空列表包含空列表。 –
'会员(Xs,Xss),会员(X,Xs)' – false