尾递归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

但是,由于list-catenation运算符@在其第一个参数的长度上采用线性时间线性,因此会产生二次时间遍历.而且,列表连接本身不是尾递归的.

因此,我们希望避免使用@.此解决方案不使用列表连接,而是通过将新映射的参数预先添加到累加器来累积:

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是尾递归的.

最后,这种方法通过累积所谓的差异列表来避免递归列表 - 连接和列表反转:

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到[]以获得映射前缀.

Answer 2

（我相信你的话，这不是家庭作业。）

答案是函数式编程中的经典模式之一，即 cons/reverse 习惯用法。首先，您以相反的顺序排列您的列表，这很容易以尾递归方式完成。最后，您反转列表。反转也是尾递归操作，因此不会对堆栈安全造成问题。

缺点是额外的分配和更笨拙的代码。

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

一个很好的锻炼是（重新）实现了一堆的“标准”列表功能（append，rev_append，fold_left，fold_right，filter，forall，等），使用这种风格使它们尾递归必要。