From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 0F1AABB81 for ; Fri, 22 Jul 2005 17:49:28 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j6MFnRtZ001759 for ; Fri, 22 Jul 2005 17:49:27 +0200 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 RAA31796 for ; Fri, 22 Jul 2005 17:49:27 +0200 (MET DST) Received: from postfix4-1.free.fr (postfix4-1.free.fr [213.228.0.62]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j6MFnQtc001755 for ; Fri, 22 Jul 2005 17:49:26 +0200 Received: from quatre.invalid (vol75-1-81-57-79-249.fbx.proxad.net [81.57.79.249]) by postfix4-1.free.fr (Postfix) with ESMTP id 76BCC319E20; Fri, 22 Jul 2005 17:49:26 +0200 (CEST) Received: from berke by quatre.invalid with local (Exim 4.50) id 1Dvzmq-0003z9-PK; Fri, 22 Jul 2005 17:50:08 +0200 Date: Fri, 22 Jul 2005 17:50:08 +0200 From: Berke Durak To: Thomas Fischbacher Cc: caml-list@inria.fr Subject: Re: [Caml-list] How to do this properly with OCaml? Message-ID: <20050722155008.GA11661@ara.zapto.org> References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.9i X-Miltered: at concorde with ID 42E11587.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 42E11586.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; berke:01 durak:01 caml-list:01 ocaml:01 ocaml:01 binary:01 heap:01 heap:01 sig:01 val:01 sig:01 mutable:01 berke:01 durak:01 -one:98 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO autolearn=disabled version=3.0.3 On Fri, Jul 22, 2005 at 04:26:55PM +0200, Thomas Fischbacher wrote: > I repeatedly stumble across problems where I would like to use a > programming style which seems quite out of line with how one is supposed > to use OCaml (to say it otherwise, it looks outright wrong and > horrendously ugly), but which nevertheless might be just appropriate for > the situation in question. So, I would like to hear the opinion of the > OCaml community about this. > > Imagine constructing a binary heap of tuples. It is somewhat neat to be > able to just use an array to store the entries of the heap which is > pre-allocated to some fixed size and replaced by a larger array whenever > more space is needed. The only thing known about the heap's entries at > compile time is that they are bound to be tuples, hence boxed objects, > but nothing else is known about their size or even type. > > As one does not have a prototype of such a tuple at the time the array is > created, it seems to me as if the best thing one could do in OCaml would > be: > > (1) Make an array of option and initially fill it with None. > > (2) Make an optional array of tuples which is None until the first entry > is made. I feel some psychorigidity here. Maybe some 3-[2-[4-(6-fluoro-1,2-benzisoxazol-3-yl)-1-piperidinyl]ethyl]-6,7,8,9- tetrahydro-2-methyl-4H-pyrido[1,2-a]pyrimidin-4-one can help ? Just joking. I'd suggest you provide a "zero" value for whatever type you want to put in your heap. That "zero" value should have a small memory footprint. This value does not need to be distinct from possible values for your heap, since the length information is required and sufficient for knowing which entries of your array are empty. You could package the whole stuff into a modules. Example : modul type ELEMENTS = sig type t val zero : t end module Heap(E : ELEMENTS) = sig type t = { a : E.t array; mutable n : int; (* count *) } let create () = { a = Array.make 256 E.zero ; n = 0 } etc. end -- Berke Durak