list - 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]) :-
    成员（E，L）。
firstdup(E, [N|L]) :-
    非成员（N，L），
    第一dup（E，L）。

成员（E，[E|_L]）。
成员（E，[_X|L]）：-
    成员（E，L）。

非成员（_E，[]）。
非成员（E，[F|Fs]）：-
    差异（E，F），
    非成员（E，Fs）。

优点是它也可以用于更一般的查询：

?- firstdup(E, [A,B,C])。
E = A，A = B；
E = A，A = C；
E = C，
B = C，
差异（A，C）；
错误的。

在这里，我们得到三个答案：A是前两个答案中的重复项，但基于两个不同的理由：A可能等于B或C。在第三个答案中，是重复的，但如果与 不同B，它只会是重复的。CA

要理解定义，请阅读:-箭头 ← 所以右侧是您所知道的，左侧是您得出的结论。在开始的时候读那个方向的谓词通常会有点烦人，毕竟你可能很想遵循“执行线程”。但通常这条线索无处可去——它变得太复杂而无法理解。

第一条规则如下：

提供的是我们得出的具有第一个重复项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]) :-
    成员（E，L）。
firstdup(E, [N|L]) :-
    地图列表（差异（N），L），
    第一dup（E，L）。

Answer 2

在这个答案中，我们改进了这个早期答案中呈现的逻辑纯代码。一步步：

1. 我们将两个谓词memberd/2和non_member/2一个谓词组合在一起memberd_t/3，它使用一个附加参数将列表成员关系具体化为真值（true或false）。

   memberd_t/3等价于memberd/2+ non_member/2，所以我们可以这样定义：

   memberd_t(X,Xs,true) :-
      成员（X，Xs）。
   memberd_t(X,Xs,false) :-
      非成员（X，Xs）。
   

   或者，反之亦然，我们可以这样定义：memberd/2non_member/2

   成员（X，Xs）：-
      memberd_t(X,Xs,true)。
   
   非成员（X，Xs）：-
      memberd_t(X,Xs,false)。
   

   memberd_t/3在实践中，我们使用具有更好确定性的优化实现。

   让我们看看它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 = 假，差异（X，1），差异（X，2），差异（X，3）。
   

2. 以谓词的以下变体firstdup/2（前面定义）作为我们的起点：

   firstdup(E,[X|Xs]) :-
      （成员（X，Xs），
         E=X      
      ; 非成员（X，Xs），
         第一次备份（E，Xs）
      ）。
   

3. 让我们memberd/2用non_member/2!memberd_t/3

   firstdup(E,[X|Xs]) :-
      ( memberd_t(X,Xs,true),
         E=X
      ; memberd_t(X,Xs,false),
         第一次备份（E，Xs）
      ）。
   

4. 让我们吊起来memberd_t/3！

   firstdup(E,[X|Xs]) :-
      memberd_t(X,Xs,T),
      (T=真
      -> E=X      
      ; T=假，
         第一次备份（E，Xs）
      ）。
   

5. 上面的模式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 ] )。
真的。% 确定性地成功

?- firstdup( X ,[ 1 ,2,3, 1 ])。
X = 1。% 确定性地成功

?- firstdup(X,[A,B,C])。% 成功，留下一个选择点
      A=X , B=X % ... 以保留完整的解决方案集。
; A=X , 差异 (B,X), C=X
; 差异（A，X），B=X，C=X
; 错误的。

Answer 3

代表（N，列表）：-追加（L1，[N|_]，列表），追加（_，[N|_]，L1），\ +（代表（_，L1））。

Answer 4

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

它说..找到所有重复项，即。其中有一个具有列表索引 I1 的项目，而另一个具有 I2 的项目，使得它们都具有相同的值 N，并且索引不同，即不要将相同的列表项目视为重复项。

这些重复项被放置在列表 AllDups 中（按照找到的顺序，从头开始），如果找到的第一个重复项与您正在检查的值 M 一致，则谓词为真。

第一次尝试：这行得通，但效率很低，建立一个所有重复的列表

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.