尾递归List.map [英] Tail recursive List.map

问题描述

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

The typical List.map function in OCaml is pretty simple, it takes a function and a list, and applies the function to each items of the list recursively. I now need to convert List.map into a tail recursive function, how can this be done? What should the accumulator accumulate?

推荐答案

可以说，最简单的方法是使用尾递归辅助功能map_aux来实现map，该辅助功能遍历该列表，同时累积一个已经映射的前缀:

Arguably the simplest approach is to implement map in terms of an tail-recursive auxiliary function map_aux that traverses the list while accumulating an already mapped prefix:

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

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

However, as the list-catenation operator @ takes time linear in the length of its first argument, this yields a quadratic-time traversal. Moreover, list catenation is itself not tail-recursive.

因此，我们要避免使用@.此解决方案不使用列表分类，而是通过将 prepending 新映射的参数累积到累加器来累积:

Hence, we want to avoid the use of @. This solution does not use list catenation, but accumulates by prepending newly mapped arguments to the accumulator:

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

To restore the mapped elements in their right order, we then simply have to reverse the accumulator in the case for the empty list. Note that List.rev is tail-recursive.

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

This approach, finally, avoids both recursive list-catenation and list reversal by accumulating a so-called 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应用于[]以获得映射的前缀.

This idea is to have the accumulated prefix list be represented by a function acc that, when applied to an argument list ys, returns the prefix list prepended to ys. Hence, as an initial value of the accumulator we have fun ys -> ys, representing an empty prefix, and in the case for [] we simply apply acc to [] to obtain the mapped prefix.

这篇关于尾递归List.map的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！