尾递归List.map

可以说最简单的方法是实现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到[]以获得映射前缀.