Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

["Kontra, Gergely" <kgergely@mlabdial.hit.bme.hu>]

>I get that the cost of list concatenation is proportional to the length of 
>the first list.  So (elem :: list) is O(1) no matter what the length of 
>list is.  But (list :: elem) is O(n), with n being the length of the list.
[...]
>An example of where this would come in usefull.  Consider the merge 
>portion of a merge sort (yes, I know I'm duplicating code that is in the 
>List module- I'm doing it so that I can learn the language.  Plus, here we 
>all understand the problem).  The current implementation I have (probably 
>chock full of inefficiencies) is:

If you want to build up a list from the beginning to the tail, just
append the new elements before the list, and then reverse the list.

(* Sorry, new to ocaml, my syntax may be SML-ish *)

(* tail-recursive function to reverse a list *)
let reverse List =
	(* returns a list like: (reverse L2) @ L1 *)
	let rec revapp L1 L2 =
		match L2 with
		| []     -> L1
		| hd::tl -> revapp hd::L1 tl
	in revapp [] List

Since reversing is not so slow, this might be, what you want.

Gergő

+-[Kontra, Gergely @ Budapest University of Technology and Economics]-+
|         Email: kgergely@mcl.hu,  kgergely@turul.eet.bme.hu          |
|  URL:   turul.eet.bme.hu/~kgergely    Mobile: (+36 20) 356 9656     |
+-------"Olyan langesz vagyok, hogy poroltoval kellene jarnom!"-------+
.
Magyar php mirror es magyar php dokumentacio: http://hu.php.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