Why wasn't OCaml List.fold_right implemented as tail-recursive?

Question

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?

Answer 1

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