13

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

2 回答 2

9

以我的经验，非平凡函数的尾递归版本经常以空间效率与时间效率为代价。换句话说，标准库中的函数对于较小的输入可能很容易更快。

于 2012-08-17T20:25:17.723 回答
9

好吧，您的代码正在堆中构建并传递闭包的“链表”（每个闭包都将前一个闭包捕获为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)）

在这种情况下，累积的东西是迄今为止的结果列表（反向），而不是闭包。但是效果是完全一样的。

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

于 2012-08-17T23:18:07.507 回答