list - Prolog 压缩列表

Question

我有一个奇怪的问题，我不知道如何解决。

我写了一个谓词，通过删除重复项来压缩列表。 所以如果输入是[a,a,a,a,b,c,c,a,a]，输出应该是[a,b,c,a]。我的第一个代码有效，但项目顺序错误。所以我添加了一个 append/3 目标，它完全停止工作了。

想不通为什么。我尝试跟踪和调试，但不知道哪里出了问题。

这是我的代码，它可以工作但是项目顺序错误:

p08([Z], X, [Z|X]).
p08([H1,H2|T], O, X) :-
    H1 \= H2,
    p08([H2|T], [H1|O], X).
p08([H1,H1|T], O, X) :-
    p08([H1|T], O, X).

这是较新的版本，但它根本不起作用:

p08([Z], X, [Z|X]).
p08([H1,H2|T], O, X) :-
    H1 \= H2,
    append(H1, O, N),
    p08([H2|T], N, X).
p08([H1,H1|T], O, X) :-
    p08([H1|T], O, X).

Answer 1

H1 不是列表，这就是 append(H1, O, N) 失败的原因。 如果将 H1 更改为 [H1]，您实际上会得到与第一个解决方案相同的解决方案。为了真正反转累加器中的列表，您应该更改前两个参数的顺序:append(O, [H1], N)。此外，您应该将第一个规则更改为与空列表 p08([], X, X) 匹配的规则(没有它，目标 p08([], [], Out) 失败)。

现在，为了解决您的问题，这是最简单的解决方案(它已经是尾递归的，正如@false 在对该答案的评论中所述，因此不需要累加器)

p([], []).                    % Rule for empty list
p([Head, Head|Rest], Out):-   % Ignore the Head if it unifies with the 2nd element
    !,                        
    p([Head|Rest], Out).
p([Head|Tail], [Head|Out]):-  % otherwise, Head must be part of the second list
    p(Tail, Out).

如果你想要一个类似于你的(使用累加器):

p08(List, Out):-p08(List, [], Out).

p08([], Acc, Acc).
p08([Head, Head|Rest], Acc, Out):-
    !,
    p08([Head|Rest], Acc, Out).
p08([Head|Tail], Acc, Out):-
    append(Acc, [Head], Acc2),
    p08(Tail, Acc2, Out).