Prolog:第一个重复值

Question

我需要在列表中找到第一个重复值.

prep(3,[1,3,5,3,5]). 应该是真的.

prep(5,[1,3,5,3,5]). 应该是假的.

我想检查与当前值和先前列表成员的相等性,直到我找到重复,如果它找到一个它将测试与X的相等但我不知道如何在Prolog中做到这一点!

我感谢任何帮助!谢谢

Answer 1

这是一个使用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.

要理解这个定义,请阅读:-箭头←那么右边的是你所知道的,左边是你得出的结论.在这方面读取谓词通常在开始时有点恼火,毕竟你可能会想要遵循"执行的线程".但通常这个线索无处可去 - 它变得太复杂而无法理解.

第一条规则如下:

提供的E是L我们得出的列表元素,它[E|L]具有E第一个副本.

第二条规则如下:

提供的E是第一个重复的L(不要惊慌这里说,我们不知道...),并提供了N不是一个元素L,我们的结论是[N|L]有E作为第一个重复.

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

Answer 2

不确定这是否是家庭作业/您可以使用哪些谓词有限制，但这会让序言为您执行递归。

它说..找到所有重复项，即。其中有一个项目的列表索引为 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.