This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

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

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

```