Just for the record, I'd like to dispell a couple of myths:

On Wednesday 16 March 2005 01:05, Yoann Padioleau wrote:
> IMHO the reason it was slow is because it used associative list (instead of
> Map) for associative access,

Although Map is asymptotically faster than List.assoc for lookup (O(ln n) vs 
O(n)), OCaml's Hashtbl and array-based equivalents are typically several 
times faster than Map.

Also, I think that many people would consider the use of an imperative data 
structure, such as a hash table, for memoizing to be the remit of functional 
programming.

On Wednesday 16 March 2005 00:18, Oliver Bandel wrote:
> which does not really looks tail recursive.
> Called more than 2 * 10^6 times...
> And many other examples...

In OCaml, non-tail-recursive functions are often faster than their tail 
recursive equivalents for small inputs (e.g. short lists). I expect that the 
functions you have identified fall into this category, so converting them to 
tail-recursive form is likely to slow the program down rather than speed it 
up.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists