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 IAA05906; Wed, 9 Apr 2003 08:53:05 +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 IAA05754 for ; Wed, 9 Apr 2003 08:53:04 +0200 (MET DST) Received: from lri.lri.fr (lri.lri.fr [129.175.15.1]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h396r3917296 for ; Wed, 9 Apr 2003 08:53:03 +0200 (MET DST) Received: from pc8-123 (mail@pc8-123 [129.175.8.123]) by lri.lri.fr (8.11.6p2/jtpda-5.3.2) with ESMTP id h396p4r26688 ; Wed, 9 Apr 2003 08:51:04 +0200 (MEST) Received: from filliatr by pc8-123 with local (Exim 3.35 #1 (Debian)) id 1939QG-00041E-00; Wed, 09 Apr 2003 08:51:04 +0200 From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <16019.49880.45938.429789@gargle.gargle.HOWL> Date: Wed, 9 Apr 2003 08:51:04 +0200 To: "Yaron M. Minsky" Cc: Caml List Subject: Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures In-Reply-To: <1049803409.3739.13.camel@dragonfly.localdomain> References: <15993.10380.206589.498703@barrow.artisan.com> <16018.7894.703716.797621@katsura.parc.xerox.com> <20030408091229.GA7467@mail4.ai.univie.ac.at> <1049803409.3739.13.camel@dragonfly.localdomain> X-Mailer: VM 7.03 under Emacs 20.7.2 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) X-MailScanner: Found to be clean X-Spam: no; 0.00; filliatre:01 lri:01 caml-list:01 glue:01 yaron:01 minsky:01 abstractions:01 argues:01 vectors:01 val:01 resizing:01 filliatr:01 arrays:01 compiler:01 dummy:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Yaron M. Minsky writes: > Resizeable arrays seem like a > pretty essential data structure, and the fact that you can't implement > them nicely without breaking the standard compiler abstractions (due to > the dummy value issue) argues in favor of including it in the > distribution, I would think. There is an easy trick for this dummy value issue. What you want is an interface looking like: ====================================================================== type 'a t (* resizeable vectors *) val create : int -> 'a t (* only initial capacity is given *) val add : 'a t -> 'a -> unit ... ====================================================================== The idea is to initially store the capacity as a negative size, thus remembering that the data array still needs initialization: ====================================================================== type 'a t = { mutable size : int; mutable data : 'a array } let create n = if n <= 0 then invalid_arg "create"; { size = -n; data = [||] } ====================================================================== Note that being empty is having a size less or equal than zero: ====================================================================== let is_empty v = v.size <= 0 ====================================================================== Then the first time an addition is performed, you allocate the array: ====================================================================== let add v x = if v.size < 0 then begin (* first addition: we allocate the array *) v.data <- Array.create (- v.size) x; v.size <- 0 end; (* code to insert x, resizing data if needed *) ... ====================================================================== Hope this helps, -- Jean-Christophe Filliātre (http://www.lri.fr/~filliatr) ------------------- 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