logo标签列表

Erlang：使用递归从列表中选择唯一项

recursionerlang
7

提供一个Erlang列表，例如：

L = [foo, bar, foo, buzz, foo].

如何使用递归函数仅显示列表中的唯一项目？我不想使用内置函数，比如列表函数之一（如果它存在的话）。

在我的示例中，我想要得到一个新的列表，其中只包含唯一的项目，例如：

SL = [bar, buzz].

我猜我会先使用快速排序函数对列表进行排序，然后再应用过滤器？

任何建议都将很有帮助。这个例子是Cesarini和Thompson的优秀书籍“Erlang编程”第3章练习的变体。

感谢您的编辑。我是 Stack Overflow 的新手，非常感谢您的建议/风格指南。 - Alexander Von Kimmelmann
@Muzaaya Joshua：我想仅显示该列表的唯一项，而不仅仅是删除重复项。 - Alexander Von Kimmelmann
9个回答
7
我建议选择这个方案：
unique(L) ->
    unique([],L).
unique(R,[]) -> R; 
unique(R,[H|T]) ->
    case member_remove(H,T,[],true) of
        {false,Nt} -> unique(R,Nt);
        {true,Nt} -> unique([H|R],Nt)
    end.

member_remove(_,[],Res,Bool) -> {Bool,Res};
member_remove(H,[H|T],Res,_) -> member_remove(H,T,Res,false);
member_remove(H,[V|T],Res,Bool) -> member_remove(H,T,[V|Res],Bool).

成员删除函数一次返回其余的尾部，而不检查重复元素和测试结果的所有出现。
非常优雅。运行得非常好。非常感谢您的回复。 - Alexander Von Kimmelmann
3
我可能会这样做：)
get_unique(L) ->
    SortedL = lists:sort(L),
    get_unique(SortedL, []).

get_unique([H | T], [H | Acc]) ->
    get_unique(T, [{dup, H} | Acc]);
get_unique([H | T], [{dup, H} | Acc]) ->
    get_unique(T, [{dup, H} | Acc]);
get_unique([H | T], [{dup, _} | Acc]) ->
    get_unique(T, [H | Acc]);
get_unique([H | T], Acc) ->
    get_unique(T, [H | Acc]);
get_unique([], [{dup, _} | Acc]) ->
    Acc;
get_unique([], Acc) ->
    Acc.
2
我认为这个想法可能是：检查您是否已经看到了列表的头部。如果是这样，则跳过它并递归检查尾部。如果没有，则将当前头部添加到结果和“已看到”，并递归检查尾部。检查是否已经看到项目的最合适结构是集合（set）。
因此，我建议以下操作：
 remove_duplicates(L) -> remove_duplicates(L,[], sets:new()). 

  remove_duplicates([],Result,_) -> Result;
  remove_duplicates([Head|Tail],Result, Seen) ->
    case sets:is_element(Head,Seen) of
      true -> remove_duplicates(Tail,Result,Seen);
      false -> remove_duplicates(Tail,[Head|Result], sets:add_element(Head,Seen))
    end.
谢谢。您的代码示例确实删除了重复项，但同时并没有仅返回列表中的唯一项？ - Alexander Von Kimmelmann
哦，我明白了。您需要在列表中仅出现一次的元素。在这种情况下，我认为您根本不需要递归函数。您只需要计算每个项目并过滤计数器等于1的元素。像这样 D = lists:foldl( fun(X,Acc) -> dict:update_counter(X,1,Acc) end, dict:new(), List), [X|| {X,1} <- dict:to_list(D)]. - Odobenus Rosmarus
1
[X||{X,1} <- dict:to_list(lists:foldl( fun(X,Acc) -> dict:update_counter(X,1,Acc) end, dict:new(), List))].将列表中的元素计数并返回一个字典，然后将字典转换为列表，并使用列表推导式过滤出计数为1的元素。 - Odobenus Rosmarus
1
unique(List) ->
    Set = sets:from_list(List),
    sets:to_list(Set).
为了提高你的回答质量，最好在解决方案中添加描述文本。 - Kalamarico
感谢您提供这段代码片段，它可能会提供一些有限的、即时的帮助。通过展示为什么这是一个好的解决方案，适当的解释将极大地提高其长期价值，并使其对未来具有类似问题的读者更有用。请编辑您的答案，添加一些解释，包括您所做的假设。 - Toby Speight
1

使用两个累加器。一个用于保留到目前为止已经看到的元素，另一个用于保存实际结果。如果您第一次看到该项目（不在Seen列表中），则将该项目添加到两个列表的开头并进行递归。如果您之前已经看过该项目，则在递归之前从结果列表（Acc）中删除它。

-module(test).

-export([uniques/1]).

uniques(L) ->
    uniques(L, [], []).

uniques([], _, Acc) ->
    lists:reverse(Acc);
uniques([X | Rest], Seen, Acc) ->
    case lists:member(X, Seen) of
        true -> uniques(Rest, Seen, lists:delete(X, Acc));
        false -> uniques(Rest, [X | Seen], [X | Acc])
    end.
我想知道是谁对正确的解决方案进行了-1操作？唯一让我困扰的是在已知项目不唯一时使用lists:delete/2。我想你可以有两个列表NotUnique和UniqueByNow，它们没有交集。你将不得不检查X是否同时存在于这两个列表中。 - Dmitry Belyaev
也许不太优雅，但仍是一个正确的解决方案。+1 - Alexander Von Kimmelmann
我确实喜欢累加器的想法 - 作为Erlang中的一般原则。以前没有想过这个。谢谢你的建议。 - Alexander Von Kimmelmann
@DmitryBelyaev 我认为你需要使用lists:delete/2，即使按照你提出的方式在第二次看到该项时从UniqueByNow中删除该项。对吗？ - cashmere
是的。我只是不喜欢对于出现超过2次的元素，使用 true -> uniques(Rest, Seen, lists:delete(X, Acc));。在这种情况下，Acc 中将没有 X。 - Dmitry Belyaev
0
unique(L) -> sets:to_list(sets:from_list(L)).
将列表L转换为集合，再将集合转换为列表，即可去除列表中的重复元素。
感谢您的贡献！请添加一些说明您的代码如何工作以及它具体做了什么。这将极大地改善您的答案。 - Hexaholic
0

这个解决方案仅从列表中过滤出重复项。可能需要进一步改进以实现您想要的功能。

remove_duplicates(List)->
    lists:reverse(removing(List,[])).
removing([],This) -> This;
removing([A|Tail],Acc) -> 
    removing(delete_all(A,Tail),[A|Acc]).
delete_all(Item, [Item | Rest_of_list]) ->
    delete_all(Item, Rest_of_list);
delete_all(Item, [Another_item| Rest_of_list]) ->
    [Another_item | delete_all(Item, Rest_of_list)];
delete_all(_, []) -> [].

编辑

微软 Windows [版本 6.1.7601] 版权所有 (c) 2009 Microsoft Corporation。保留所有权利。
C:\Windows\System32>erl Eshell V5.9 (按 ^G 可跳出) 1> List = [1,2,3,4,a,b,e,r,a,b,v,3,2,1,g,{red,green},d,2,5,6,1,4,6,5,{red,green}]. [1,2,3,4,a,b,e,r,a,b,v,3,2,1,g, {red,green}, d,2,5,6,1,4,6,5, {red,green}] 2> remove_duplicates(List). [1,2,3,4,a,b,e,r,v,g,{red,green},d,5,6] 3>
去除重复项并不能给你独特的元素。试试他的例子。如果你想要移除重复集合：to_list(sets:from_list(List)) 可能比这个更好。 - cashmere
@MuzaayaJoshua 作者想要移除所有不唯一的元素。[a, a, b, b, c, d] 只应保留 [c, d]。 - Dmitry Belyaev
@MuzaayaJoshua 作者想要 [foo, bar, foo, buzz, foo] => [bar, buzz]。你的解决方案给出了 [foo, bar, foo, buzz, foo] => [foo, bar, buz]。我提出了使用集合的解决方案，因为你说在一些项目中使用过。 - cashmere
我仍然坚持我的观点：删除重复项并不能让你得到列表中的唯一项。请再次阅读问题。亚历山大不想删除重复项，他想找出哪些元素只出现了一次。至少我会用适当的理由进行投票反对。 - cashmere
感谢您提供的代码示例，它当然帮助我更好地学习了Erlang。不过我倾向于同意cashmere的看法，即您的示例确实去除了重复项，但同时并没有给出我想要的独特项。 - Alexander Von Kimmelmann
0

请尝试以下代码

-module(util).

-export([unique_list/1]).

unique_list([]) -> [];
unique_list(L)  -> unique_list(L, []).

% Base Case
unique_list([], Acc) -> 
    lists:reverse(Acc);

% Recursive Part 
unique_list([H|T], Acc) ->
    case lists:any(fun(X) -> X == H end, T) of
        true  -> 
            unique_list(lists:delete(H,T), Acc);
        false -> 
            unique_list(T, [H|Acc])
end.
-1

最简单的方法是使用一个带有“累加器”的函数来跟踪您已经拥有的元素。 因此，您可以编写以下函数：

% unique_acc(累加器, 待取出的列表).

通过不导出累加器版本，而是导出其调用者，仍然可以拥有一个清晰的函数：

-module(uniqueness).
-export([unique/1]).

unique(List) ->
    unique_acc([], List).

如果要取出的列表为空，则完成：
unique_acc(Accumulator, []) ->
    Accumulator;

如果不是：

unique_acc(Accumulator, [X|Xs]) ->
   case lists:member(X, Accumulator) of
       true  -> unique_acc(Accumulator, Xs);
       false -> unique_acc([X|Accumulator], Xs)
   end.

需要注意的两件事情:
-- 这里使用了一个列表内置函数 -- lists:member/2。你也可以自己很容易地编写它。
-- 元素的顺序已经被反转，从原始列表到结果。如果不喜欢这样，可以将unique/1定义为lists:reverse(unique_acc([], List))。或者更好的是，自己编写一个反转函数！(很容易)。

这将从列表中删除重复项，但不提供唯一项。在case语句中，您应该执行 true -> unique_acc(lists:delete(X, Accumulator), Xs); 。即使如此，它仅适用于项出现偶数次的情况，并对奇数次出现失败。 - cashmere
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接