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] Probably FAQ: Why is list-append (list :: elem) so expensive?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2002-09-26 (14:57)
From: Kontra, Gergely <kgergely@m...>
Subject: Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?
>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.


+-[Kontra, Gergely @ Budapest University of Technology and Economics]-+
|         Email:,          |
|  URL:    Mobile: (+36 20) 356 9656     |
+-------"Olyan langesz vagyok, hogy poroltoval kellene jarnom!"-------+
Magyar php mirror es magyar php dokumentacio:

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