0

作为昨天问题 Erlang 的后续：使用递归从列表中选择唯一项目

在 Erlang 中，假设我想从给定列表中选择所有唯一项目，例如

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

我使用了你的代码示例导致

NewList = [bar, buzz].

我将如何NewList在 Erlang 中进一步操作？

例如，假设我不仅想从 中选择所有唯一项目，还想计算来自?List的所有结果项目的字符总数。NewList

4

3 回答 3

5

在函数式编程中，我们有频繁出现的模式，它们应该有自己的名字和支持函数。最广泛使用的两个是map和fold（有时reduce）。这两个构成了列表操作的基本构建块，通常不需要编写专用的递归函数。

地图

该map函数按顺序遍历列表，生成一个新列表，其中每个元素都是将函数应用于原始列表中的相应元素的结果。以下是典型的map实现方式：

map(Fun, [H|T]) -> % recursive case
    [Fun(H)|map(Fun, T)];
map(_Fun, []) -> % base case
    [].

这是递归函数的完美介绍性示例；粗略地说，函数子句要么是递归情况（导致调用 iself并带有较小的问题实例），要么是基本情况（没有进行递归调用）。

那你怎么用map？请注意，第一个参数Fun应该是一个函数。在 Erlang 中，可以内联声明匿名函数（有时称为 lambdas）。例如，要对列表中的每个数字求平方，生成一个平方列表：

map(fun(X) -> X*X end, [1,2,3]). % => [1,4,9]

这是高阶编程的一个例子。

请注意，这map是 Erlang 标准库的一部分，因为lists:map/2.

折叠

虽然map在一个列表和另一个列表之间创建 1:1 元素映射，但目的fold是将某些函数应用于列表的每个元素，同时累积单个结果，例如总和。正确的折叠（它有助于将其视为“向右”）可能看起来像这样：

foldr(Fun, Acc, [H|T]) -> % recursive case
    foldr(Fun, Fun(H, Acc), T);
foldr(_Fun, Acc, []) -> % base case
    Acc.

使用此函数，我们可以对列表的元素求和：

foldr(fun(X, Sum) -> Sum + X, 0, [1,2,3,4,5]). %% => 15

注意foldr和foldl都是lists模块中 Erlang 标准库的一部分。

map虽然它可能不是很明显，但可以单独使用和解决一大类常见的列表操作问题fold。

递归思考

编写递归算法起初可能看起来令人生畏，但当你习惯它时，它会变得很自然。遇到问题时，您应该确定两件事：

  1. 如何将问题分解为更小的实例？为了使递归有用，递归调用必须将较小的问题作为其参数，否则函数将永远不会终止。
  2. 基本情况是什么，即终止标准？

至于1），考虑计算一个列表的元素的问题。这怎么可能分解成更小的子问题呢？好吧，这样想：给定一个非空列表，它的第一个元素（头）是 X，余数（尾）是 Y，它的长度是 1 + Y 的长度。由于 Y 小于列表 [X |Y]，我们已经成功地减少了这个问题。

继续列表示例，我们什么时候停止？好吧，最终，尾巴将是空的。我们回到基本情况，即空列表的长度为零的定义。您会发现为各种情况编写函数子句非常类似于为字典编写定义：

%% Definition:
%% The length of a list whose head is H and whose tail is T is
%% 1 + the length of T.
length([H|T]) ->
    1 + length(T);
%% Definition: The length of the empty list ([]) is zero.
length([]) ->
    0.
于 2013-03-14T23:23:30.813 回答
2

您可以使用折叠来递归结果列表。为简单起见，我将您的原子转换为字符串（您可以使用 list_to_atom/1 执行此操作）：

1> NewList = ["bar", "buzz"].
["bar","buzz"]
2> L = lists:foldl(fun (W, Acc) -> [{W, length(W)}|Acc] end, [], NewList).        
[{"buzz",4},{"bar",3}]

这将返回一个 proplist，您可以像这样访问：

3> proplists:get_value("buzz", L).
4
于 2013-03-14T20:05:58.613 回答
0

如果您想自己构建递归以用于教学目的而不是使用列表：

count_char_in_list([], Count) ->
    Count;
count_char_in_list([Head | Tail], Count) ->
    count_char_in_list(Tail, Count + length(Head)). % a string is just a list of numbers

进而：

1> test:count_char_in_list(["bar", "buzz"], 0).
7
于 2013-03-14T20:36:48.480 回答