我需要在列表中找到第一个重复值。
prep(3,[1,3,5,3,5]).
应该是真的。
prep(5,[1,3,5,3,5]).
应该是假的。
我想检查与当前值和先前列表成员的相等性,直到我找到重复,如果它找到一个它将测试与X的相等但我不知道如何在Prolog中做到这一点!
我感谢任何帮助!谢谢
这是一个使用dif/2
的纯版本,它实现了声音不等式。 dif/2
由B-Prolog,YAP-Prolog,SICStus-Prolog和SWI-Prolog提供。
firstdup(E, [E|L]) :- member(E, L). firstdup(E, [N|L]) :- non_member(N, L), firstdup(E, L). member(E, [E|_L]). member(E, [_X|L]) :- member(E, L). non_member(_E, []). non_member(E, [F|Fs]) :- dif(E, F), non_member(E, Fs).
优点是它也可以用于更一般的查询:
?- firstdup(E, [A,B,C]). E = A, A = B ; E = A, A = C ; E = C, B = C, dif(A, C) ; false.
在这里,我们得到三个答案:A
是前两个答案中的副本,但有两个不同的理由:A
可能等于B
或C
。在第三个答案中,B
是副本,但如果C
与A
不同,它将只是重复。
要理解这个定义,请阅读:-
作为箭头←所以右边的是你所知道的,左边是你得出的结论。在这方面读取谓词通常在开始时有点恼火,毕竟你可能会想要遵循“执行的线程”。但通常这个线索无处可去 - 它变得太复杂而无法理解。
第一条规则如下:
ProvidedE
is an element of listL
we conclude that[E|L]
hasE
as first duplicate.
第二条规则如下:
ProvidedE
is the first duplicate ofL
(don't panic here and say we don't know that ...) and provided thatN
is not an element ofL
we conclude that[N|L]
hasE
as first duplicate.
member/2
谓词在许多Prolog系统中提供,non_member(X,L)
可以定义为maplist(dif(X),L)
。因此,人们会将firstdup/2
定义为:
firstdup(E, [E|L]) :- member(E, L). firstdup(E, [N|L]) :- maplist(dif(N), L), firstdup(E, L).
在这个答案中,我们改进了this earlier answer中提供的逻辑纯代码。一步步:
memberd/2
和non_member/2
组合成一个memberd_t/3
,它使用一个额外的参数将列表成员资格统一为真值(true
或false
)。
memberd_t/3
相当于memberd/2
+ non_member/2
,所以我们可以这样定义:
memberd_t(X,Xs,true): - memberd(X,Xs)。 memberd_t(X,Xs,false): - non_member(X,Xs)。
或者,反之亦然,我们可以像这样定义memberd/2
和non_member/2
:
memberd(X,Xs): - memberd_t(X,Xs,true)。 non_member(X,Xs): - memberd_t(X,Xs,false)。
在实践中,我们使用memberd_t/3
-one的调整实现,具有更好的确定性。
让我们看看memberd_t/3
实际上涵盖了memberd/2
和non_member/2
!
? - memberd_t(X,[1,2,3],T)。 T =真,X = 1; T =真,X = 2; T =真,X = 3; T =假,dif(X,1),dif(X,2),dif(X,3)。firstdup/2
(defined earlier)的以下变体为出发点:
firstdup(E,[X | Xs]): - (memberd(X,Xs),E = X; non_member(X,Xs),firstdup(E,Xs))。memberd/2
替换non_member/2
和memberd_t/3
的用法!
firstdup(E,[X | Xs]): - (memberd_t(X,Xs,true),E = X; memberd_t(X,Xs,false),firstdup(E,Xs))。memberd_t/3
!
firstdup(E,[X | Xs]): - memberd_t(X,Xs,T),(T = true - > E = X; T = false,firstdup(E,Xs))。pred_t(OtherArgs,T), (T = true -> Then ; T = false, Else)
可以用if_/3
更简洁地表达,写if_(pred_t(OtherArgs),Then,Else)
。
firstdup(E,[X | Xs]): - if_(memberd_t(X,Xs),E = X,firstdup(E,Xs))。让我们运行一些查询!
?- firstdup(1,[1,2,3,1]). true. % succeeds deterministically ?- firstdup(X,[1,2,3,1]). X = 1. % succeeds deterministically ?- firstdup(X,[A,B,C]). % succeeds, leaving behind a choicepoint A=X , B=X % ... to preserve the full solution set. ; A=X , dif(B,X), C=X ; dif(A,X), B=X , C=X ; false.
rep(N,List): - 追加(L1,[N | _],List),追加(_,[N | _],L1),\ +(rep(_,L1))。
不确定这是否是作业/对你可以使用哪些谓词有限制,但这可以为你做递归。
它说..找到所有重复,即。其中有一个带有列表索引I1的项目,另一个带有I2,这样它们都具有相同的值N,并且索引也不相同。即不要将相同的列表项视为重复项。
在列表AllDups中放置这些重复项(按照从一开始就找到的顺序),如果找到的第一个重复项与您正在检查的值M结合,则谓词为true。
第一次尝试:这有效,但效率非常低,构建了所有重复项的列表
prep(M, List) :-
findall(N,
(nth0(I1, List, N),
nth0(I2, List, N),
not(I1 =:= I2)),
AllDups),
nth1(1, AllDups, M).
?- prep(3,[1,3,5,3,5]).
true.
?- prep(5,[1,3,5,3,5]).
false.
即使您不被允许使用findall,它也可能帮助您找出如何“手动”进行操作。
第二次尝试:这不起作用/回溯太远会产生误报
您甚至可以在没有findall的情况下执行此操作 - 使用nth0查找第一个重复项,然后如果它与您正在检查的值结合,则返回true,否则返回false。
prep(N, List) :-
nth0(I1, List, N),
nth0(I2, List, N),
not(I1 =:= I2).
第三次尝试:这有效,并在找到第一个副本后立即返回
prep(M, List) :-
nth0(I1, List, N),
nth0(I2, List, N),
not(I1 =:= I2), !,
M == N.