[Caml-list] List.rev

[skaller <skaller@users.sourceforge.net>]

On Sat, 2004-05-01 at 05:08, Karl Zilles wrote:
> Rahul Siddharthan 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???

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

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.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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