为什么OCaml std lib有这么多非尾递归函数？

Question

我最近一直在重写许多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)

Answer 1

根据我的经验,尾部递归版本的非平凡函数通常会将空间效率与时间效率相提并论.换句话说,对于小输入,标准库中的函数可能会更快.

Answer 2

好吧,您的代码正在构建并传递闭包的"链接列表"(每个闭包捕获前一个闭包k),而不是调用堆栈上的一堆帧.

以递归方式执行它的更常见,等效的方法是到目前为止传递结果列表(反过来,因为你只能有效地添加到前面),然后在最后反转它:

let map f l =
  let rec aux l acc = match l with
      []   -> List.rev acc
    | a::l -> aux l (f a :: l)
  in aux l

(这基本上是一样的List.rev (List.rev_map f l))

在这种情况下,累积的东西是到目前为止(反向)的结果列表,而不是闭包.但效果完全一样.

在这两种情况下,我们需要线性空间用于某种中间表示(输入和输出列表除外),因此就内存使用的复杂性而言,没有优于非尾递归版本的优势.虽然堆上的内存确实比堆栈多,但是使用尾递归版本可能比非尾递归版本更适用于更大的列表.就绝对内存使用而言,累积list选项可能是最有效的,因为闭包和堆栈帧都有更多的开销.