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
[Caml-list] "List.index" or "List.unique" functions?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-05-01 (04:18)
From: Jon Harrop <jdh30@c...>
Subject: Re: [Caml-list] List.rev
On Saturday 01 May 2004 02:59, skaller wrote:
> > List.rev is not tail recursive, so you wouldn't want to use this
> > function on industrial size lists.
> But it should be. Why isn't it???

I'm not sure that it isn't already tail-recursive. Doesn't the second argument 
in rev_append act as an accumulator?

> let rev lst = let r = ref [] in
>   let rec aux lst = match lst with
>   | [] -> !r
>   | h::t -> r:= h :: !r; aux t

let rev l = fold_left (fun t h -> h::t) [] l


> BTW: documentation that says a function is 'tail recursive'
> is misguided. That's an implementation detail of no
> possible use to a user of the function. The user may
> benefit from knowing the complexity of the function
> in terms of speed and auxilliary storage required.

As "tail recursive" typically means less stack storage and more heap storage 
instead of the reverse, it is useful to a user and it does pertain to the 
complexity (although it obviously doesn't quantify the complexity of the heap 


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