Why does the OCaml std lib have so many non-tail-recursive functions?

Question

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.

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

I have rewritten it to be:

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)

Chaffer

Isint CPS version of the functions more efficient than tail-recursive versions? – Gonick

@Gonick CPS version of a recursive function is necessarily tail-recursive. – Chaffer

The map function is a case of tail recursion modulo cons. – Premed

Answer 1

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.

Mustee

How is this tradeoff made? I would imagine the cost of pushing and popping stack frames in recursive functions that don't get tail-call elimination would lead to worse efficiency both in space and time. Is it not so? – Boarding

Well, very often the tail recursive version of a list function builds up the result in reverse, then reverses it at the end. For a short input, the non-tail-recursive version avoids the reversal. Generalized continuation passing can create a lot of closures (or so I would imagine). – Mustee

Answer 2

Well, your code is building and passing along a "linked list" of closures (each of the closures captures the previous one as k) in the heap instead of a stack of frames on the call stack.

A more common, equivalent way to do it tail-recursively is to pass along the result list so far (in reverse, since you can only efficiently add to the front), and then reverse it in the end:

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

(this is basically the same as List.rev (List.rev_map f l))

In this case, the thing that is accumulated is the list of results so far (in reverse), rather than a closure. But the effect is exactly the same.

In both cases we need linear space for some kind of intermediate representation (other than the input nor the output list), so in terms of complexity of memory usage, there is no advantage over the non-tail-recursive version. Although it is true that there is more memory on the heap than the stack, so using the tail-recursive version will probably work for bigger lists than the non-tail-recursive version. In terms of absolute memory usage, the accumulating the list option is probably the most efficient, because closures and stack frames both have more overhead.

Joyner