Re: [Caml-list] List.rev

[Jon Harrop <jdh30@cam.ac.uk>]

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

=:-p

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

Cheers,
Jon.

-------------------
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