列表的常用递归模式

列表的常用递归模式

尽管一个典型的程序往往会使用很多不同的函数来操作列表，但大多数列表处理函数都是由少数几种模式演变而来。大部分列表处理函数无非就是在干着这些事情：

• 在一个列表中寻找一个元素，并在找到时做些事情。
• 对输入列表的每个元素做些事情并构造一个与其结构相同的输出列表。
• 在遇到列表中的第 n 个元素时做些事情。
• 对列表进行扫描，并构造一个或一组与原列表相关的新列表。我们将以此对其进行讨论。

搜索列表元素

给定以下递归模式：

search(X, [X|T]) ->
    ... do something ...
    ...;
search(X, [_|T]) ->
    search(X, T);
search(X, []) ->
    ... didn't find it ...

第一种情况匹配的是找到了我们所感兴趣的项的情形。第二种情况在列表的头部不是我们所感兴趣的项时匹配，这时将接着处理列表的尾部。最后一种情况匹配的是列表元素耗尽的情形。

将以上代码与member/2的代码（第??节）作个比较，我们可以看到我们不过是把…dosomething…换成了true，把…didn'tfindit…换成了false。

构建同构列表

有时我们会想构造一个形如 输入列表的列表，但同时又要对输入列表的每个元素做些操作。这时可以这么写：

isomorphic([X|T]) ->
    [something(X)|isomorphic(T)];
isomorphic([]) ->
    [].

然后，比如我们想写一个将给定列表中的所有元素翻倍的函数，我们就可以这么写：

double([H|T]) ->
    [2 * H | double(T)];
double([]) ->
    [].

于是便有：

> lists1:double([1,7,3,9,12]).
[2,14,6,18,24]

事实上这种手法只能作用于列表的最上层 ，因此如果我们想遍历列表的所有层次，我们就得将函数定义修改如下：

double([H|T]) when integer(H)->
    [2 * H | double(T)];
double([H|T]) when list(H) ->
    [double(H) | double(T)];
double([]) ->
    [].

后一个版本就可以成功遍历深层的嵌套列表了：

> lists1:double([1,2,[3,4],[5,[6,12],3]]).
[2,4,[6,8],[10,[12,24],6]]

计数

我们常常要使用到计数器，以便对一个列表的第 n 个元素做些动作：

count(Terminal, L) ->
    ... do something ...;
count(N, [_|L]) ->
    count(N-1, L).

则返回列表中第 n 个元素（假设其存在）的函数可以写成：

nth(1, [H|T]) ->
    H;
nth(N, [_|T]) ->
    nth(N - 1, T).

这种递减至一个终止条件的计数方式往往要由于递增计数。为了说明这一点，考虑同样是返回第 n 个元素但是采用递增计数的函数nth1：

nth1(N, L) ->
    nth1(1, N, L).
nth1(Max, Max, [H|_]) ->
    H;
nth1(N, Max, [_|T]) ->
    nth1(N+1, Max, T).

这种做法需要一个额外的参数和一个辅助函数。

收集列表元素

现在我们希望对一个列表中的元素做些动作，生成一个或一组新的列表。对应的模式如下：

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

collect([H|T], Accumulator) ->
    case pred(H) of
        true ->
            collect(T, [dosomething(H)|Accumulator]);
        false ->
            collect(T, Accumulator)
    end;
collect([], Accumulator) ->
    Accumulator.

在这里我们引入了一个多出一个参数的辅助函数，多出的这个参数用于存储最终要被返回给调用方的列表。

借助这样一种模式，举个例子，我们可以写这样的一个函数：计算输入列表的所有偶元素的平方并删除所有奇元素：

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

funny([H|T], Accumulator) ->
    case even(H) of
        true -> funny(T, [H*H|Accumulator]);
        false -> funny(T, Accumulator)
    end;
funny([], Accumulator) ->
    Accumulator.

于是有：

> lists:funny([1,2,3,4,5,6])
[36,16,4]

注意在这种情况下结果列表中的元素的顺序与原列表中对应元素的顺序是相反的。

在递归过程中使用累加列表来构造结果经常是一种推荐的做法。这样可以编写出运行时只适用常数空间的扁平 的代码（细节参见第??节）。