从列表中删除重复项并保留最右边的出现次数。

Question

我正在尝试从列表中删除重复项，同时保留最右边的出现次数。例如：[1,2,3,1,2] 转换为 [3,1,2]。这是我在 Prolog 中的第一次尝试，我不明白我做错了什么。它总是返回 false。这是我的代码：

%nrap(L:list,E:element,S:integer)
%L - the initial list, list of integers
%E - the element, integer
%S - the result, nrap of E in L, S integer
%flow model: (i,i,o),(i,i,i)

nrap([],_,0).
nrap([H|T],E,S):-
    H=E,
    nrap(T,E,S1),
    S is S1+1.
nrap([H|T],E,S):-
    H\=E,
    nrap(T,E,S).

%transform(L:list,L2:list,R:list)
%L - the initial list, list of integers
%L2 - copy of the initial list
%R - the resulted list, without duplicates, list of integers
%flow model: (i,i,o),(i,i,i)

transform([],[],[]).
transform([H|T],L2,[H|R]):-
    nrap(L2,H,S),
    S=1,
    transform(T,L2,R).
transform([H|T],L2,R):-
    nrap(L2,H,S),
    S>1,
    transform(T,L2,R).

- DianaM

---

你的 transform/3 失败是因为第二个参数 L2 从未被“驱动”到空列表 []，而你的基本情况假设了这一点。 L2 永远不会改变。尝试将 transform([],_,[]) 作为你的基本情况。 - lurker

@lurker，它确实说“按最后出现的顺序”，所以至少是一致的。 - user1812457

@Boris 啊，我没注意到那个。谢谢。 - lurker

现在你已经改变了基本情况，仍然需要更仔细地查看 L2。你在递归过程中一直使用相同的 L2。由于你正在计算 L2 中的元素数量，因此元素数量 S 在整个过程中永远不会改变。这将无法成功处理 S = 1 的情况。 - lurker

在编写代码以删除重复项时，最好始终指定如何测试重复项，即使用相等性或使用统一性，如果您的列表可能包含非地面术语。这里可能是这种情况吗？ - Paulo Moura

Answer 1

我应该纯洁还是不纯洁？如果我们可以轻松地保存逻辑纯度，为什么要考虑牺牲它呢！
使用memberd_t/3和if_/3，我们定义list_rset/2及其左侧的“孪生”list_lset/2：

list_rset([], []).                     % 保留最右边的出现
list_rset([E|Es], Rs0) :-
   if_(memberd_t(E, Es),
       Rs0 = Rs,
       Rs0 = [E|Rs]),
   list_rset(Es, Rs).

list_lset([], []).                     % 保留最左边的出现
list_lset([E|Es], Ls) :-
   post_pre_lset(Es, [E], Ls).         % 使用内部辅助谓词

post_pre_lset([], _, []).            
post_pre_lset([E|Es], Pre, Ls0) :-     % 第二个参数：向前查找的累加器
   if_(memberd_t(E, Pre),
       Ls0 = Ls,
       Ls0 = [E|Ls]),
   post_pre_lset(Es, [E|Pre], Ls).

让我们运行一些查询！

?- _Es = [1,2,3,1,2], list_lset(_Es, Ls), list_rset(_Es, Rs).
Ls = [1,2,3], Rs = [3,1,2].           % 成功地确定

在上面的查询中，1在列表[1,2,3,1,2]的开头和结尾都在2之前。
如果1在开头时在2之前，但在结尾时在其后面呢（例如[1,2,3,2,1]）？

？- _Es = [1,2,3,2,1]，list_lset(_Es，Ls)，list_rset(_Es，Rs)。
Ls = [1,2,3]，Rs = [3,2,1]。％成功确定性地

接下来，我们看一下使用仅包含变量的列表的更一般的list_rset/2目标。
感谢@PauloMoura的建议！

?- Es = [A,B,C,A,B], list_rset(Es,Rs).
   Es = [C,C,C,C,C], Rs = [    C],     A=B ,               B=C
;  Es = [B,B,C,B,B], Rs = [C,  B],     A=B ,           dif(B,C)
;  Es = [C,B,C,C,B], Rs = [  C,B],               A=C , dif(B,C)
;  Es = [A,C,C,A,C], Rs = [  A,C],           dif(A,C),     B=C
;  Es = [A,B,C,A,B], Rs = [C,A,B], dif(A,B), dif(A,C), dif(B,C).

以上剩余目标是什么意思？ 如果没有足够的实例化，dif/2 是不可判定的。 为了保证逻辑正确性，执行prolog-dif约束被延迟。

最后，再介绍一个用例：一个既有变量又有地面术语的“输入”列表Xs。

?- Es = [A,B,z], list_rset(Es,Rs).
   当Es=[A,B,z]时，调用list_rset(Es,Rs)函数。
   若Rs=[z]，则A=B，B=z。
   若Rs=[B,z]，则A=B，B≠z。
   若Rs=[B,z]，则A=z，B≠z。
   若Rs=[A,z]，则A≠z，B=z。
   若Rs=[A,B,z]，则A≠B，A≠z，B≠z。

- repeat

---

重申一遍，我期望你能做到严谨的逻辑纯粹性！(+1) :) - lurker

考虑到您对逻辑纯度的关注，您是否尝试过使用类似 list_rset([A,B,C,A,B],Xs) 的目标来测试您的解决方案？ - Paulo Moura

@PauloMoura 非常有帮助！我明天（其实是今天）会更新答案，添加你提供的案例和一些使用变量的类似案例。 （我还将尝试展示如何基于list_rset/2构建一些方便谓词的纯模拟，与更直接的方法进行比较。）谢谢！ - repeat

Answer 2

这是对之前答案的跟进...在此答案中，我们使用dcg！ 我们基于memberd_t/3和if_//3构建lset//1——dcg的类比if_/3：

lset([]) -->
   [].
lset([X|Xs]) -->
   [X],
   lset_pre(Xs,[X]).

lset_pre([],_) -->
   [].
lset_pre([X|Xs],Pre) -->
   if_(memberd_t(X,Pre), [], [X]),
   lset_pre(Xs,[X|Pre]).

同样适用于rset//1:

rset([]) -->
   [].
rset([X|Xs]) -->
   if_(memberd_t(X,Xs), [], [X]),
   rset(Xs).

一些示例查询:

?- _Es = [1,2,3,1,2], phrase(lset(_Es),Ls), phrase(rset(_Es),Rs).
Ls = [1,2,3], Rs = [3,1,2].               % succeeds deterministically

?- _Es = [1,2,3,2,1], phrase(lset(_Es),Ls), phrase(rset(_Es),Rs).
Ls = [1,2,3], Rs = [3,2,1].               % succeeds deterministically

- repeat

Answer 3

这比你想象的要简单。由于“集合”中的元素必须按照最后出现的顺序排列，因此您根本不需要保留列表的副本：只需与列表的其余部分（尾部）进行比较。

如果您知道第一个列表总是会被固定的（例如，所有元素都是整数），您可以编写以下代码：

list_set([], []).
list_set([X|Xs], Ys0) :-
    (   memberchk(X, Xs)
    ->  Ys0 = Ys
    ;   Ys0 = [X|Ys]
    ),
    list_set(Xs, Ys).

memberchk/2 可以用来检查一个 ground term 是否在一个 ground terms 的列表中。它将会成功或失败一次。

更通用的解决方案是，提出一个约束条件，即如果一个元素与其后面的所有元素都不同，则该元素应该在集合中；否则该元素应该被丢弃：

list_set([], []).
list_set([X|Xs], [X|Ys]) :-
    maplist(dif(X), Xs),
    list_set(Xs, Ys).
list_set([X|Xs], Ys) :-
    \+ maplist(dif(X), Xs),
    list_set(Xs, Ys).

在这里，maplist(dif(X), Xs) 的意思是：

X 与列表 Xs（尾部）中的每个元素都不同。

而且如果 \+ Goal 成功，则 Goal 不会成功。

有了这个定义：

?- list_set([1,2,3,1,2], S).
S = [3, 1, 2] ;
false.

?- list_set([1,2,3,3,1,1,2], S).
S = [3, 1, 2] ;
false.

?- list_set([A,B,C,A,B],Xs).
Xs = [C, A, B],
dif(A, B),
dif(C, B),
dif(C, A) ;
false.

- user1812457

---

将任何类型的协同处理与元逻辑谓词混合使用，会导致失去声明性语义！假设您使用 dif/2 作为 (\==)/2 的声明性替代方案，那么为什么紧接着又要使用 (\+)/1 并将声明性语义抛出窗外？确实非常令人困惑。 - repeat

@Boris：Prolog的合取是纯单调子集的逻辑合取，这也是Prolog名称的由来。 - false

@Boris：如果纯洁感觉像束缚你的直接夹克，那么实际编程错误会感觉如何呢？ - false

我看到当（使用基础术语）你的list_set/2的第一个定义是有意义的。然而，为了防止不良使用，前提条件需要被积极执行，可以通过静态代码分析或动态术语测试来实现，例如：groundlist_set(Xs,Ys) :- ( ground(Xs) -> list_to_set_aux(Xs,Ys) ; throw(error(instantiation_error,groundlist_set/2) ). - repeat

是的，你说过了。在我看来，OP并没有要求实现，而是对他自己的代码有疑问...按照这个标准，你的回答和我的回答都不太准确 :) - repeat