为什么OCaml std lib具有这么多的非尾递归函数? [英] Why does the OCaml std lib have so many non-tail-recursive functions?

问题描述

最近，我一直在重写许多OCaml标准库函数以进行尾递归.鉴于这需要进行直接的CPS转换，我不解为什么不以这种方式编写默认版本.

I have been rewriting many OCaml standard library functions to be tail-recursive lately. Given that this has entailed straight-forward CPS transformation, I am left puzzling over why the default versions are not written this way.

例如，在标准库中，map定义为:

As an example, in the standard library, map is defined as:

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)

推荐答案

以我的经验，非平凡函数的尾部递归版本通常会在空间效率与时间效率之间进行权衡.换句话说，对于较小的输入，标准库中的函数可能很容易更快.

In my experience, tail recursive versions of non-trivial functions often trade space efficiency against time efficiency. In other words, the functions in the standard library might easily be faster for smallish inputs.

这篇关于为什么OCaml std lib具有这么多的非尾递归函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！