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

[Markus Mottl <markus@oefai.at>]

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.

In case you want to learn more about purely functional datastructures,
you will definitely want to read Chris Okasaki's book "Purely Functional
Data Structures", which is published by Cambridge University Press (1998).

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