我最近一直在重写许多 OCaml 标准库函数,使其成为尾递归的。鉴于这需要直接的 CPS 转换,我对为什么默认版本没有以这种方式编写感到困惑。
例如,在标准库中,map 定义为:
let rec map f = function
[] -> []
| a::l -> let r = f a in r :: map f l
我已经将其改写为:
let map f l =
let rec aux l k = match l with
[] -> k []
| a::l -> aux l (fun rest -> k (f a :: rest))
in aux l (fun x -> x)
最佳答案
根据我的经验,非平凡函数的尾递归版本通常会在空间效率与时间效率之间进行权衡。换句话说,对于较小的输入,标准库中的函数可能会更快。
关于ocaml - 为什么 OCaml std lib 有这么多非尾递归函数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12012585/