Return 只包含重复元素的列表

Question

不允许我使用任何内置的 ProLog 列表谓词。 我刚开始使用 ProLog 并进行了以下练习：

写一个谓词 repeated(L,D) 其中 D 是一个列表列表 L.

中所有重复的值

?- repeated([a,b,a,d,a,d],D).
D = [a,d].

请帮忙，我已经坚持了很长时间了 :// 谢谢！

Answer 1

分解一下。大多数递归问题都有 1 或 2 个特殊的终止情况和一般情况。

所以...

特殊的终止情况是空列表。它不包含重复项：

repeated( [] , [] ) .

一般情况是这样的：

列表的头部重复，当且仅当...

可以在列表的尾部找到。

所以，我们需要一种方法来识别骗子：

is_duplicate(X,Xs) :- \+ contains(X,Xs) .

contains(X, [X|Xs] ).
contains(X, [_|Xs] ) :- contains(X,Xs).

[顺便提一下，contains/2本质上是内置member/2的实现。]

一旦我们有了它，实现一般的递归情况就很容易了。我们只是遍历列表并找到重复项：

repeated( [X|Xs] , [X|Ds] ) :- is_duplicate(X,Xs), !, repeated(Xs,Ds) .
repeated( [_|Xs] ,    Ds  ) :- repeated(Xs,Ds).

剪切 (!/0) 是为了消除选择点：如果 X 是重复的，我们不想在回溯时尝试第三个/最后一个选择。

如果你把它们放在一起，你会得到这个：

repeated( []     , []     ) .
repeated( [X|Xs] , [X|Ds] ) :- is_duplicate(X,Xs), !, repeated(Xs,Ds) .
repeated( [_|Xs] ,    Ds  ) :- repeated(Xs,Ds).

is_duplicate(X,Xs) :- \+ contains(X,Xs) .

contains(X, [X|Xs] ).
contains(X, [_|Xs] ) :- contains(X,Xs).

Answer 2

似乎建议的答案不完全输出 [a, d]，而是 [b, a, d].

然而，在他的启发下，我更新了逻辑，这里是工作代码：

repeated( []     , []     ) .
repeated( [X|Xs] , [X|Ds] ) :- 
    repeated(Xs, Ds), 
    contains(X, Xs), negate(contains(X, Ds)), !.      % <--- New logic here
repeated( [_|Xs] ,    Ds  ) :- repeated(Xs, Ds).

contains(X, [X|_] ).
contains(X, [_|Xs] ) :- contains(X,Xs).
negate(X) :- \+ X.

修改后的逻辑是确保第一个元素X在列表Xs中有重复项。并且也确保它不在“return”列表Ds.

中

工作查询示例：

?- repeated([a,b,a,23,1432,5,25,23,23,24,23,25,25,21,d,a,d], D).
D = [a, 23, 25, d]
?- repeated([a, b, b, b, b], D).
D = [b]

contains/2 只是 member/2.

的自定义实现

negate/1 只是 not/1.

的自定义实现

Return 只包含重复元素的列表

Return a list that only includes duplicate elements

list

prolog