list - 尾递归List.map

Question

OCaml中典型的List.map函数非常简单，它接受一个函数和一个列表，然后将该函数递归应用于列表的每个项目。我现在需要将List.map转换为尾部递归函数，该怎么做？累加器应累加什么？

Answer 1

可以说，最简单的方法是根据尾递归辅助函数map来实现map_aux，该函数在存储已映射前缀的同时遍历列表:

let map f l =
  let rec map_aux acc = function
    | [] -> acc
    | x :: xs -> map_aux (acc @ [f x]) xs
  in
  map_aux [] l

但是，由于列表分类运算符 @在其第一个参数的长度上采用线性时间，因此产生了二次时间遍历。而且，列表分类本身不是尾递归的。

因此，我们要避免使用 @。此解决方案不使用列表分类，而是通过将新映射的参数放在累加器之前进行累加:

let map f l =
  let rec map_aux acc = function
    | [] -> List.rev acc
    | x :: xs -> map_aux (f x :: acc) xs
  in
  map_aux [] l

为了以正确的顺序还原映射的元素，我们只需要在清空列表的情况下反转累加器即可。注意 List.rev是尾递归的。

最后，这种方法通过累积所谓的 difference list避免了递归列表分类和列表反转:

let map f l =
  let rec map_aux acc = function
    | [] -> acc []
    | x :: xs -> map_aux (fun ys -> acc (f x :: ys)) xs
  in
  map_aux (fun ys -> ys) l

这个想法是让累积的前缀列表由函数 acc表示，该函数在应用于参数列表 ys时，返回前缀在 ys的前缀列表。因此，作为累加器的初始值，我们有 fun ys -> ys，它表示一个空前缀，在 []的情况下，我们只需将 acc应用于 []即可获得映射的前缀。