On Wed, 16 Mar 2005, Jacques Garrigue wrote:
> From: Yoann Padioleau <padiolea@irisa.fr>
> > Jon Harrop <jon@ffconsultancy.com> writes:
> > > In OCaml, non-tail-recursive functions are often faster than their tail
> > > recursive equivalents for small inputs (e.g. short lists).
> >
> > really ? why ?
>
> Because tail-recursive versions do some extra work to ensure
> tail-recursiveness. For instance building a list in reverse order, and
> converting it back with List.rev at the end. This only pays off for
> huge lists.

No doubt the implementors will want me guillotined for bringing this up again,
but using the (still functional!) set_cdr! tail recursive functions, which do
*not* reverse the list, are always faster than the non tail recursive
list functions, even for small lists, at least in my experience. So I suspect
that your "for instance" is in fact the only reason for the disparity. I'd
welcome a counterexample.

Those Obj based List functions are what ExtLib provides, I think, and there are
even ways to get this optimization neatly into ML style languages. Maybe in ML
20XY this will be addressed.

-- Brian