6.7.3 实现列表函数

刚才我们看到的筛选和映射函数，没有展示如何实现，现在，我们要看一个在第三章开始创建的函数。因为所有的列表处理函数都有类似的结构，看过下面的示例以后，实现其他任何函数也是可能的。

在第三章，我们写的函数，能够计算列表中的所有元素的和或积；随后，我们就意识到它可能比开始所表现的更有用：我们看到，它还能用来查找最小或最大元素。那时，我们没有讨论过泛型，因此，函数只处理整数。在清单 6.22 中，有一个类似的函数，没有类型批注，原始约束自动泛型化。

清单 6.22 泛型列表聚合 (F# Interactive)

> let rec fold f init list =

  match list with

   |[] –> init

   |head::tail –>

    let state = f init head

    fold f state tail

;;

val fold : (‘a -> ‘b -> ‘a) -> ‘a-> ‘b list -> ‘a    [1] <-- 显示的类型签名

这个实现非常像第三章的；更重要的是，我们去掉了类型批注，因此，推断的签名更通用[1]。现在函数参数列表值的类型为 ‘b，聚合产生的值可以有不同类型（类型参数为 ‘a）。处理函数的参数值为当前的聚合结果（类型为 ‘a），和列表（‘b）中的一个元素，返回一个新的聚合的结果。

我们很快会看到，使用泛型使聚合更有用；在 F# 库中也有，处理不可变 F# 列表类型的版本位于 List 模块。下面的代码片断显示了原来第三章中的用法，计算列表中所有元素的积：

> [ 1 .. 5 ] |> List.fold (*) 1

val it : int = 120

由于将要处理泛型函数，编译器必须首先推断出类型参数的类型。这里，我们处理的是整数列表，所以，参数 ‘b 是 int，结果也是整数，所以 ‘a 也是 int。清单 6.23 显示其他一些使用 fold 的例子。

清单 6.23 使用 fold 的示例 (F# Interactive)

> places |> List.fold (fun sum (_,pop) -> sum + pop) 0;;    [1]

val it : int = 9080788

> places |> List.fold (fun s (n, _)-> s + n + ", ") "";;   [2]

val it : string =

"Seattle, Prague, New York,Grantchester, Cambridge, "

> places

    |> List.fold (fun (b,str) (name, _) –>    [3]

          let n = if b then name.PadRight(20) else name + "\n"

          (not b, str+n)

        ) (true, "")    <-- 指定初始元组值

    |> snd    [4]

    |> printfn "%s";;   <-- 输出格式化后的字符串

Seattle Prague

New York Grantchester

Cambridge

在所有示例中，我们使用的都是我们定义的有关城市信息的集合，因此，列表的类型都相同。这样，参数 ‘b 的实际类型总是 (string * int) 元组；然而，聚合的结果不同。第一种情况[1]，我们只计算人口的和，因此，结果的类型是 int；第二个示例[2]，我们要构建有城市名字的字符串，因此，用空字符串开始聚合。lambda 函数作为第一个参数值，追加当前处理的城市名字和分隔符。

在最后一个示例中[3]，我们实现的版本改进了格式，将城市名字分成两列，因此，lambda 函数执行两个交替操作。第一种情况，用空格填充名字（填充第一列），第二种情况，则将添加换行符（以结束行）。这是通过使用 bool 类型的临时值完成的，最初设置为 true，然后，在每次迭代时切换。聚合后的值包含了交替的临时值和结果字符串，因此，在结束时，需要从元组中删除临时值。

6.7.3 实现列表函数