OCaml中典型的List.map函数非常简单,它接受一个函数和一个列表,然后将该函数递归应用于列表的每个项目。我现在需要将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
但是,由于列表分类运算符
@
在其第一个参数的长度上采用线性时间,因此产生了二次时间遍历。而且,列表分类本身不是尾递归的。因此,我们要避免使用
@
。此解决方案不使用列表分类,而是通过将新映射的参数放在累加器之前进行累加: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
应用于[]
即可获得映射的前缀。
关于list - 尾递归List.map,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27386520/