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-25 (16:17) From: Markus Mottl Subject: Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?
```On Wed, 25 Sep 2002, Brian Hurt wrote:
> 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.

You probably mean (list @ [elem]).

> Why doesn't Ocaml keep a pointer to the last element of the list,
> as well as the first element?

Because standard lists are purely functional, i.e. you can't just
overwrite some pointer to append an element. If there are several lists
that share a common sublist, such an operation would change both lists.

E.g.:

let l = [1; 2; 3] in
let l1 = 0 :: l in
let l2 = 42 :: l in
l @ [4]

If the last operation overwrote anything in "l", this would also change
l1 and l2, thus destroying referential transparency: list variables
couldn't be used for straightforward equational reasoning anymore,
which is important if you want to e.g. proof list algorithms correct.

As you noted, keeping pointers to the previous element also makes
list nodes larger and thus more expensive both in terms of time and
space. Why have this by default if lists are most often not used in ways
that require efficiency with such operations?

If you want to have mutable lists, it's not difficult to implement them.
But be warned: you might be surprised to discover that standard lists
most often perform better in not too extreme cases.

you will definitely want to read Chris Okasaki's book "Purely Functional

Regards,
Markus Mottl

--
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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

```