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

Question

跟进昨天的问题Erlang:使用递归从列表中选择唯一项

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

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

我用了你的代码示例导致

NewList = [bar, buzz].

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

例如,假设我不仅要从中选择所有唯一项目List,还要计算所有结果项目的总字符数NewList？

Answer 1

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

地图

该map函数按顺序迭代列表,生成一个新列表,其中每个元素是将函数应用于原始列表中相应元素的结果.以下是典型的map实现方式:

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

这是递归函数的完美介绍示例; 粗略地说,函数子句要么是递归的情况(导致调用自身与较小的问题实例)或基本情况(没有进行递归调用).

那你怎么用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模块.

虽然它可能不是很明显,但是可以使用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.