7

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?

Jackson Tale
  • 25,428
  • 34
  • 149
  • 271

2 Answers2

11

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

gasche
  • 31,259
  • 3
  • 78
  • 100
  • Do you have any evidence that tail recursive versions are slower? I'm not convinced... :-) – J D Jun 14 '13 at 16:48
  • The easy way to make `fold_right` tail-recursive, as done by the original post above, is to reverse the list first, then use fold_left. This has a cost that is easy to measure on benchmarks. More sophisticated techniques are available, such as using a counter alongside the usual traversal, and only `rev`-ing the rest of the list for fold-left when the counter passes a tresholf; this allows to have a very small overhead for small lists. We've implemented this [in Batteries](https://github.com/ocaml-batteries-team/batteries-included/blob/master/src/batList.ml#L380) and the performance is okay. – gasche Jun 14 '13 at 16:58
11

This question has been asked before, probably many times. You can read some previous answers here:

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

My quick answer is that the non-tail-recursive implementation is often a lot faster for smallish cases. The implementors obviously thought this was a good tradeoff.

Community
  • 1
  • 1
Jeffrey Scofield
  • 65,646
  • 2
  • 72
  • 108