Prolog：使用其他列表的重复元素构建列表

Question

我需要构造一个接收列表的谓词，检查谁是重复元素和 return 其他列表。示例：

?- rep_elements([a,b,c,a,b,d], Xs).
Xs = [a,b].

我开始构建一个基本结构，但我现在不知道如何完成这个谓词，或者如果这是更好的方法：

exists(Elem, [Elem|_]).
exists(Elem, [H|T]) :-
    exists(Elem, T).

rep_elements([], []).
rep_elements([H|T], [Y|Z]) :-
    exists(H, T),
    rep_elements(T, Z).

有什么建议吗？

Answer 1

rep_elements/2 缺少对非重复元素的处理。

如果exists/2 也'return' 删除找到的重复项后的列表T，那么我们可以使用清理后的列表进行递归，任务就完成了。当然，exists/2 应该变成 exists/3，并可能重命名为更好、更具描述性的名称。

Answer 2

让我们逐步重新编写您的代码！

谓词 exists/2 被广泛使用的 member/2 涵盖。让我们用那个一个！

rep_elements([], []).
rep_elements([H|T], [Y|Z]) :-
   member(H, T),
   rep_elements(T, Z).

, rep_elements/2 is missing a clause; we add one using non_member/2!

rep_elements([H|T], Z) :-
   non_member(T,H),
   rep_elements(T,Z).

重新运行 OP 给出的查询！

?- rep_elements([a,b,c,a,b,d],Xs).
  Xs = [a,b]
; false.

好的！我们完了吗？不完全的！考虑以下查询和我们得到的答案：

?- rep_elements([a,a,a,a,b],Xs).
  Xs = [a,a,a]                 % (1) duplicate items are retained
; Xs = [a,a,a]                 % (2) redundant answer
; Xs = [a,a,a]                 % (2)
; Xs = [a,a,a]                 % (2)
; Xs = [a,a,a]                 % (2)
; Xs = [a,a,a]                 % (2)
; false.                       % (3) leaves behind useless choicepoint

下一步是什么？退后一步，制定规范！

Answer 3

首先，我建议我们使用更具描述性的谓词名称，list_uniqdups。

我们根据meta-predicate tpartition/4, if_/3 and (=)/3定义list_uniqdups/2:

list_uniqdups([],[]).
list_uniqdups([X|Xs0],Ys0) :-
   tpartition(=(X),Xs0,Es,Xs),
   if_(Es=[], Ys0=Ys, Ys0=[X|Ys]),
   list_uniqdups(Xs,Ys).

示例查询：

?- list_uniqdups([a,b,c,a,b,d],Xs).  % query as given by the OP
Xs = [a,b].                          % expected result

?- list_uniqdups([a,c,b,a,b,d],Xs).  % similar query
Xs = [a,b].                          % same result

?- list_uniqdups([b,c,a,a,b,d],Xs).  % now, `b` comes before `a`
Xs = [b,a].                          % retain the original order

?- list_uniqdups([a,a,a,a,b],Xs).
Xs = [a].                            % remove all duplicates

请注意，以上所有查询都确定性地成功。

Answer 4

您可以递归检查列表的头部是否在列表的尾部，然后将其添加到结果中。您的解决方案可以修改为：

exists(Elem, [Elem|_]).
exists(Elem, [H|T]) :-
     exists(Elem, T).
/* IF you get empty list*/
rep_elements([], []).

/* If repetition found in list then joining it to head of list*/
rep_elements([H|T], Result) :-
     exists(H, T),
     rep_elements(T, [H|Result]).

/* If head of list is not found in the Tail of list*/
rep_elements(H|T, Result):-
     not(exists(H,T)),
     rep_elements(T,Result).

这应该有效。

Prolog：使用其他列表的重复元素构建列表

Prolog: Build a list with repeated elements of other list

list

prolog