Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
RE: [Caml-list] @, List.append, and tail recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-01-30 (15:54)
From: Brian Hurt <brian.hurt@q...>
Subject: Re: [Caml-list] @, List.append, and tail recursion
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 

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


To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: