为什么OCaml标准库有这么多非尾递归函数？

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)

- efrey

---

CPS版本的函数是否比尾递归版本更高效？ - Gab

@Gab CPS版本的递归函数必须是尾递归的。 - efrey

map函数是尾递归模cons的一个例子。 - sdcvvc

Answer 1

根据我的经验，非平凡函数的尾递归版本通常在时间效率和空间效率之间进行权衡。换句话说，对于较小的输入，标准库中的函数可能更快。

- Jeffrey Scofield

---

这个权衡是如何做出的？我想象在没有尾递归消除的递归函数中推送和弹出堆栈帧的成本会导致空间和时间上的效率变差。难道不是这样吗？ - Chuck

经常情况下，列表函数的尾递归版本会先倒序地构建结果，然后在最后将其翻转。对于短输入而言，非尾递归版本避免了此次翻转。一般化的延续传递可能会创建许多闭包（至少我是这样想的）。 - Jeffrey Scofield

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) 相同）

在这种情况下，累积的是到目前为止的结果列表（反向），而不是闭包。但效果完全相同。

在两种情况下，我们都需要线性空间以某种中间表示形式（而不是输入或输出列表），因此从内存使用复杂性的角度来看，与非尾递归版本没有优势。虽然堆上有更多的内存，但使用尾递归版本可能适用于比非尾递归版本更大的列表。在绝对内存使用方面，累积列表选项可能是最有效的，因为闭包和堆栈帧都有更多开销。

- newacct