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 QAA21559; Fri, 22 Oct 2004 16:31:18 +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 QAA21526 for ; Fri, 22 Oct 2004 16:31:17 +0200 (MET DST) Received: from mail.davidb.org (adsl-64-172-240-129.dsl.sndg02.pacbell.net [64.172.240.129]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i9MEVEnK017490 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Fri, 22 Oct 2004 16:31:16 +0200 Received: from davidb by mail.davidb.org with local (Exim 4.42 #1 (Debian)) id 1CL0Rk-0002mw-8D; Fri, 22 Oct 2004 07:31:12 -0700 Date: Fri, 22 Oct 2004 07:31:12 -0700 From: David Brown To: skaller Cc: Jon Harrop , caml-list Subject: Re: [Caml-list] Polymorphism and the "for" loop Message-ID: <20041022143112.GA10586@old.davidb.org> References: <1098425963.7584.9.camel@pelican.wigram> <200410220838.49340.jon@jdh30.plus.com> <1098453745.7584.58.camel@pelican.wigram> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1098453745.7584.58.camel@pelican.wigram> User-Agent: Mutt/1.5.6i X-Miltered: at nez-perce with ID 417919B2.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 caml-list:01 2004:99 extensional:01 degenerate:01 dummy:01 ocaml:01 null:01 null:01 int:01 int:01 polymorphic:01 node:02 compile:02 tree:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sat, Oct 23, 2004 at 12:02:26AM +1000, skaller wrote: > > type 'a 'b tree = Leaf of 'a | Node of 'b * 'a 'b tree * 'a 'b tree > > > > Does a "unit unit tree" take up less space than a "int int tree"? > > No, this isn't possible usually, because any polymorphic > algorithm using this data structure expects a fixed > layout in memory. > > So in this case, a dummy value must exist. > > This problem can't arise in Felix or C++, because > they both use extensional polymorphism > (compile time instantiation). > > The only way this might work in Ocaml is if > the pointer to value was replaced by NULL, > but that would require a NULL check, and slow > down the algorithm for all types just to save > some memory in degenerate cases. The value of type 'unit' is kind of like a NULL. It isn't a pointer, it is an integer value. A leaf of an (int, int) tree for the value (Leaf 42) would look like (where each line is a word): +------+ |header| +------+ |85 | +------+ For an (unit, unit) tree, the value for (Leaf ()) would look like: +------+ |header| +------+ |1 | +------+ For a ((int, int), (int, int)) tree, the value will be a pointer to the pair (Leaf (4, 5)) (which must be boxed): +------+ |header| +------+ |ptr |---+ +------+ | | +----------------+ | +--> +------+ |header| +------+ |9 | +------+ |11 | +------+ So, storing the unit type is the same efficiency as storing an int type, both of which take less heap space than storing most other types. Dave ------------------- 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