在Erlang中返回相邻的重复元素

Question

我正在尝试学习Erlang中的递归，并正在阅读一本书。但是，当我遇到将一个列表转换为只包含重复元素的问题时，我卡住了。我尝试编写一个函数，它返回唯一的元素，然后从原始列表中删除它们。

adjacent_dups(L) -> L -- uniques(L).

uniques([])    -> [];
uniques([H|T]) -> [H | [X || X <- uniques(T), X /= H]].

然而，当列表结构不良好时，这种方法将无法给出正确的结果。

L = [7,3,4,3]

我的代码将返回

adjacent_dups([7,3,4,3]) -> 3 

我该如何获得？

adjacent_dups([7,3,4,3]) -> [] 

- Capa

---

这个说明不够具体：对于例如[2,3,3,4,1,1]，你期望得到什么输出结果，结果是否需要排序。对于[6,4,4,4,3,1,1,1,1]，应该怎么处理？还有[1,2,3,3,4,3,3]呢？请提供更多明确的信息。 - Peer Stritzinger

这实际上是一个非常类似的问题，与Dave Thomas去年在ElixirConf上提到的问题非常相似。以下是演讲相关部分的链接：https://youtu.be/5hDVftaPQwY?t=12m18s - Stratus3D

Answer 1

使用函数头中的模式匹配来查找相邻的相同值：

adjacent_dups(L) ->
    adjacent_dups(L, #{}).
adjacent_dups([], Acc) ->
    maps:keys(Acc);
adjacent_dups([H,H|T], Acc) ->
    adjacent_dups(T,maps:put(H,H,Acc));
adjacent_dups([_|T], Acc) ->
    adjacent_dups(T, Acc).

第一个函数adjacent_dups/1是要被导出的。其余的adjacent_dups/2是辅助函数。

adjacent_dups/1函数创建一个空映射，将其作为累加器的初始值传递给adjacent_dups/2。递归函数通常使用累加器。

adjacent_dups/2的第一个子句处理输入列表已经耗尽或为空的情况。在这种情况下，我们检索累加器映射的键；这些是我们相邻的值。

adjacent_dups/2的第二个子句处理相邻值的情况，使用模式匹配。在这种情况下，我们将该值作为键和值添加到累加器映射中，并使用列表的尾部递归调用自己。使用映射可以消除最终结果中的重复项。

adjacent_dups/2的最后一个子句处理一个值没有相邻值的情况；它只是使用列表的尾部和未修改的累加器进行递归调用。

- Steve Vinoski

---

答案已经解释了地图可以让我们从结果中消除重复项。使用它们意味着无需检查值是否已被看到；相反，只需将其添加到地图中即可。如果我们使用列表，我们将不得不为每个累加器插入遍历列表，以查看它是否已经存在，如果已经存在，则不添加。 - Steve Vinoski

根据规范的具体要求而定，问题在问题描述中未明确说明。此解决方案仅输出每个重复值一次，并以任意顺序输出。 - Peer Stritzinger

标题要求一件事，而问题又要求另一件事。 - Steve Vinoski

问题在于，映射具有O(log(N))的访问时间。这并不比使用lists:usort排序结果更好，但是更加复杂。 - Lol4t0

Answer 2

如果你只想要相邻的重复项，可以尝试从列表中逐对匹配它们。下面是一个简单的解决方案可供参考。它假设重复项仅以成对出现（例如不可能连续出现三个重复项）:

adjacent_dups([]) -> [];
adjacent_dups([A,A|Tail]) -> [A|adjacent_dups(Tail)];
adjacent_dups([_Head|Tail]) -> adjacent_dups(Tail).

如果我们再仔细思考一下，我们可能会意识到我们可以以同样的方式处理三元组。通过让该情况仅使用第一个值并将其他两个值放回，我们实际上可以使其足够通用，即使有超过两个相邻的值也可以工作。看看这个神奇的方法：

adjacent_dups([]) -> [];
adjacent_dups([A,A,A|Tail]) -> adjacent_dups([A,A|Tail]);
adjacent_dups([A,A|Tail]) -> [A|adjacent_dups(Tail)];
adjacent_dups([_Head|Tail]) -> adjacent_dups(Tail).

这是输出结果：

adjacent_dups([1,1,1,1,2,3,4,55,55,6,7,8,8,8,1]).
[1,55,8]

- Emil Vikström