Why wasn't OCaml List.fold_right implemented as tail-recursive?
functional-programming, ocaml
Solution
This tail-recursive implementation it possible to apply `fold_right` to larger lists, but at the cost of being slower for shorter lists as you have to traverse the list twice. The original developers judged that allowing extreme use cases for lists (if you have thousands of elements, you should plan for a more efficient data structure anyway) at the cost of both uglier code and making everyone else's performances worse was not a good trade-off.
There are a lot of different ways to have tail-recursive map, fold_right etc. You'll find them in the library that extend the standard library, the venerable Extlib, and the newer Batteries and Core. The implementation techniques go from yours, to tricks using a non-tailrec version optimistically for the first thousand or so of items, and then switching to a tailrec version, to ugly unsafe tricks to do a single traversal at the cost of cons cell mutation (which also decrease performances).
Problem
`List.fold_right` is not `tail-recursive` as indicated here http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html My question is why `List.fold_right` was not implemented as `tail-recursive`? I think it is not hard to do so ``` let rev l = let rec revr acc = function | [] -> acc | hd::tl -> revr (hd::acc) tl in revr [] l;; let fold_right f l b = let rev_l = rev l in let rec folder_rr acc = function | [] -> acc | hd::tl -> folder_rr (f hd acc) tl in folder_rr b rev_l;; ``` I also found in the library, a number of functions are not `tail-recursive` while they can be implemented as `tail-recursive`. How did the maker make such decisions?