Re: [Caml-list] @, List.append, and tail recursion

[Brian Hurt <brian.hurt@qlogic.com>]

On Thu, 30 Jan 2003, Christophe Raffalli wrote:

> To compute append l1 l2 in a tail recursive way the only solution I see 
> (in a pure functionnal program) is to traverse l1 twice (to reverse it 
> first), which replaces using memory on the stack by using memory to 
> build an intermediate list (and this use more memory ?).

In a purely functional way, yes.

> 
> Usually in recursive program, when you limit youself to tail recursive 
> function, you have often to reverse list and lisp languages always 
> provide the rev_append function which is tail recursive and very often 
> what you need (often l1 is an accumulator and is naturaly reversed 
> compared with l2).

This traverses the list twice, and worse yet, allocates the list twice 
(once backwards, once forwards).  Which makes it slower than tail 
recursion.

Actually, the data structures with a hole optimization is more general 
than even I was thinking of.   Read the paper.

> 
> May be rev_append could be added to the list module (despite the fact it 
> is trivial to write it yoursleft) ?

Already there.

I am, when I have the time, staring at the ocaml code generation code, 
trying to get my mind around it.  I hope to eventually have something, but 
don't expect it soon. :-)

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners