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 UAA05686; Sat, 1 May 2004 20:05:11 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA05695 for ; Sat, 1 May 2004 20:05:09 +0200 (MET DST) Received: from aomori.annexia.org (annexia.force9.co.uk [212.56.101.183]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i41I58EV005226 for ; Sat, 1 May 2004 20:05:08 +0200 Received: from rich by aomori.annexia.org with local (Exim 3.36 #1 (Debian)) id 1BJyrM-0004QT-00 for ; Sat, 01 May 2004 19:05:08 +0100 Date: Sat, 1 May 2004 19:05:08 +0100 Cc: caml-list@inria.fr Subject: Re: [Caml-list] Reading a large text file Message-ID: <20040501180508.GA16958@redhat.com> References: <20040428152813.47355.qmail@web60608.mail.yahoo.com> <20040501154351.GA5218@online.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20040501154351.GA5218@online.fr> User-Agent: Mutt/1.5.5.1+cvs20040105i From: Richard Jones X-Miltered: at nez-perce with ID 4093E6D4.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 2004:99 0400,:01 2004:99 appending:01 immutable:01 disadvantage:01 bug:01 mylist:01 mylist:01 val:01 val:01 autoconf:01 automake:01 compiles:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sat, May 01, 2004 at 11:43:51AM -0400, Rahul Siddharthan wrote: > Brian Hurt said on May 1, 2004 at 09:03:56: > > But what I'm guessing is happening is that you are appending (adding to > > the end of) your list, and that this is what is killing you. To add an > > element to the *end* of a list, Ocaml has to completely reallocate the > > entire list- turning what you might think is an O(1) operation into an > > O(n) operation. > > I'm pretty puzzled by that: why would it have to do that? Arrays, > yes, but lists, can't it just traverse the existing list to its end > and then add a new element? It's still O(n) but no reallocation. The short answer is no, because in OCaml (unlike in LISP) lists are immutable. In LISP terminology, there's no way to 'set cdr' on an OCaml 'cons structure'. The disadvantage to this is that you can't do certain destructive operations on lists, like you can so easily in LISP. The advantage is that you can't do certain destructive operations on lists! In other words, your code is more likely to be bug free. However, OCaml is a practical language and so allows you to create a mutable cons structure if you so desire. eg: # type 'a mylist = { head : 'a; mutable tail : 'a mylist option };; type 'a mylist = { head : 'a; mutable tail : 'a mylist option; } # let xs = { head = 10; tail = None };; val xs : int mylist = {head = 10; tail = None} # let xs = { head = 5; tail = Some xs};; val xs : int mylist = {head = 5; tail = Some {head = 10; tail = None}} # let ys = { head = 20; tail = None };; (* new tail *) val ys : int mylist = {head = 20; tail = None} # xs.tail <- Some ys;; (* replace tail of xs *) - : unit = () # xs;; - : int mylist = {head = 5; tail = Some {head = 20; tail = None}} Rich. -- Richard Jones. http://www.annexia.org/ http://www.j-london.com/ Merjis Ltd. http://www.merjis.com/ - improving website return on investment MAKE+ is a sane replacement for GNU autoconf/automake. One script compiles, RPMs, pkgs etc. Linux, BSD, Solaris. http://www.annexia.org/freeware/makeplus/ ------------------- 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