From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA13943; Wed, 25 Sep 2002 18:17:07 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA13939 for ; Wed, 25 Sep 2002 18:17:05 +0200 (MET DST) Received: from fichte.ai.univie.ac.at (fichte.ai.univie.ac.at [131.130.174.156]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id g8PGH4501196 for ; Wed, 25 Sep 2002 18:17:04 +0200 (MET DST) Received: from fichte.ai.univie.ac.at (markus@localhost [127.0.0.1]) by fichte.ai.univie.ac.at (8.12.3/8.12.3/Debian -4) with ESMTP id g8PGH3EI021021; Wed, 25 Sep 2002 18:17:03 +0200 Received: (from markus@localhost) by fichte.ai.univie.ac.at (8.12.3/8.12.3/Debian -4) id g8PGH3qm021020; Wed, 25 Sep 2002 18:17:03 +0200 Date: Wed, 25 Sep 2002 18:17:03 +0200 From: Markus Mottl To: Brian Hurt Cc: Ocaml Mailing List Subject: Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive? Message-ID: <20020925161703.GC31883@fichte.ai.univie.ac.at> Mail-Followup-To: Brian Hurt , Ocaml Mailing List References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.4i Organization: Austrian Research Institute for Artificial Intelligence Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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