Browse thread
[Caml-list] "List.index" or "List.unique" functions?
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ 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 =:-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