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)
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.