Menu
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)
910
Tail-recursive functions are considered better than non-tail-recursive functions — the compiler can easily optimize the tail-recursive function as there is nothing left to do in the current function after the recursive call. Hence, the function's stack frame need not be saved.
Non-Tail / Head Recursion A function is called the non-tail or head recursive if a function makes a recursive call itself, the recursive call will be the first statement in the function. It means there should be no statement or operation is called before the recursive calls.
Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call.
The tail recursion is better than non-tail recursion. As there is no task left after the recursive call, it will be easier for the compiler to optimize the code. When one function is called, its address is stored inside the stack. So if it is tail recursion, then storing addresses into stack is not needed.
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.
190
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
