我开始学习prolog(我使用SWI-prolog),我做了一个简单的练习,其中我有2个列表,我想计算他们的交集和联合.这是我的代码工作得很好,但我问自己是否有更好的方法,因为我不喜欢使用CUT运算符.
intersectionTR(_, [], []).
intersectionTR([], _, []).
intersectionTR([H1|T1], L2, [H1|L]):-
member(H1, L2),
intersectionTR(T1, L2, L), !.
intersectionTR([_|T1], L2, L):-
intersectionTR(T1, L2, L).
intersection(L1, L2):-
intersectionTR(L1, L2, L),
write(L).
unionTR([], [], []).
unionTR([], [H2|T2], [H2|L]):-
intersectionTR(T2, L, Res),
Res = [],
unionTR([], T2, L),
!.
unionTR([], [_|T2], L):-
unionTR([], T2, L),
!.
unionTR([H1|T1], L2, L):-
intersectionTR([H1], L, Res),
Res \= [],
unionTR(T1, L2, L).
unionTR([H1|T1], L2, [H1|L]):-
unionTR(T1, L2, L).
union(L1, L2):-
unionTR(L1, L2, L),
write(L).
请记住,我想只有1个结果,而不是多个结果(即使是正确的),所以运行代码:
?- intersect([1,3,5,2,4] ,[6,1,2]).
应退出:
[1,2]
true.
而不是
[1,2]
true ;
[1,2]
true ;
etc...
同样必须对union谓词有效.
正如我所说,我的代码工作得很好,但请建议更好的方法来做到这一点.
谢谢
此外,不确定为什么你死了反对削减,只要他们的删除不会改变代码的声明含义,根据你的链接.例如:
inter([], _, []).
inter([H1|T1], L2, [H1|Res]) :-
member(H1, L2),
inter(T1, L2, Res).
inter([_|T1], L2, Res) :-
inter(T1, L2, Res).
test(X):-
inter([1,3,5,2,4], [6,1,2], X), !.
test(X).
X = [1, 2].
在我调用代码的测试位中,我只是说做交集,但我只对第一个答案感兴趣.谓词定义本身没有削减.
以下是根据我以前的答案以列表(序言),删除重复 ; 其基本思想是,反过来,基于@虚假的答案,以Prolog的联盟AUBUC.
我想传达给你什么信息？
if_/3和(=)/3逻辑上纯粹的实现可以
if_/3并且(=)/3 在内部使用元逻辑Prolog功能,但(从外部)表现逻辑上纯粹.以下答案中的以下实现list_list_intersection/3和list_list_union/3使用list_item_isMember/3以及list_item_subtracted/3定义:
list_list_union([],Bs,Bs).
list_list_union([A|As],Bs1,[A|Cs]) :-
list_item_subtracted(Bs1,A,Bs),
list_list_union(As,Bs,Cs).
list_list_intersection([],_,[]).
list_list_intersection([A|As],Bs,Cs1) :-
if_(list_item_isMember(Bs,A), Cs1 = [A|Cs], Cs1 = Cs),
list_list_intersection(As,Bs,Cs).
以下是您在问题中发布的查询:
?- list_list_intersection([1,3,5,2,4],[6,1,2],Intersection).
Intersection = [1, 2]. % succeeds deterministically
让我们尝试别的......以下两个查询在逻辑上应该是等价的:
?- A=1,B=3, list_list_intersection([1,3,5,2,4],[A,B],Intersection).
A = 1,
B = 3,
Intersection = [1, 3].
?- list_list_intersection([1,3,5,2,4],[A,B],Intersection),A=1,B=3.
A = 1,
B = 3,
Intersection = [1, 3] ;
false.
而......底线是？
既不list_list_union(As,Bs,Cs)也不list_list_intersection(As,Bs,Cs)保证Cs不包含重复.如果这困扰你,代码需要适应.
以下是一些带有As和/或Bs包含重复项的查询(和答案):
?- list_list_intersection([1,3,5,7,1,3,5,7],[1,2,3,1,2,3],Cs).
Cs = [1, 3, 1, 3].
?- list_list_intersection([1,2,3],[1,1,1,1],Cs).
Cs = [1].
?- list_list_union([1,3,5,1,3,5],[1,2,3,1,2,3],Cs).
Cs = [1, 3, 5, 1, 3, 5, 2, 2].
?- list_list_union([1,2,3],[1,1,1,1],Cs).
Cs = [1, 2, 3].
?- list_list_union([1,1,1,1],[1,2,3],Cs).
Cs = [1, 1, 1, 1, 2, 3].
为了完整起见,这里是我们如何强制执行交集和联合设置---这是不包含任何重复元素的列表.
以下代码非常简单:
list_list_intersectionSet([],_,[]).
list_list_intersectionSet([A|As1],Bs,Cs1) :-
if_(list_item_isMember(Bs,A), Cs1 = [A|Cs], Cs1 = Cs),
list_item_subtracted(As1,A,As),
list_list_intersectionSet(As,Bs,Cs).
list_list_unionSet([],Bs1,Bs) :-
list_setB(Bs1,Bs).
list_list_unionSet([A|As1],Bs1,[A|Cs]) :-
list_item_subtracted(As1,A,As),
list_item_subtracted(Bs1,A,Bs),
list_list_unionSet(As,Bs,Cs).
请注意,这list_list_unionSet/3是基于此处list_setB/2定义的.
现在让我们看看两者list_list_intersectionSet/3并list_list_unionSet/3在行动:
?- list_list_unionSet([1,2,3,1,2,3,3,2,1],[4,5,6,2,7,7,7],Xs).
Xs = [1, 2, 3, 4, 5, 6, 7].
?- list_list_intersectionSet([1,2,3,1,2,3,3,2,1],[4,5,6,2,7,7,7],Xs).
Xs = [2].
以下是来自@ GuyCoder评论的附加查询(以及它的两个变体):
?- list_list_unionSet(Xs,[],[a,b]). Xs = [a,b] ; Xs = [a,b,b] ; Xs = [a,b,b,b] ... ?- list_list_unionSet([],Xs,[a,b]). Xs = [a,b] ; Xs = [a,b,b] ; Xs = [a,b,b,b] ... ?- list_list_unionSet(Xs,Ys,[a,b]). Xs = [], Ys = [a,b] ; Xs = [], Ys = [a,b,b] ; Xs = [], Ys = [a,b,b,b] ...
对于旧版本list_item_subtracted/3,上面的查询没有存在性终止.
他们做了新的.由于解决方案集大小是无限的,因此这些查询都不会普遍终止.