From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 41B38BB84 for ; Sun, 14 Dec 2008 00:24:51 +0100 (CET) X-IronPort-AV: E=Sophos;i="4.36,217,1228086000"; d="scan'208";a="21227971" Received: from discorde.inria.fr ([192.93.2.38]) by mail1-smtp-roc.national.inria.fr with ESMTP; 14 Dec 2008 00:24:51 +0100 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id mBDNOo8W000332 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Sun, 14 Dec 2008 00:24:50 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: At0CAPjSQ0mB1w3Nhmdsb2JhbACTUQEBAQoLCgcQBro2gn2Ddw X-IronPort-AV: E=Sophos;i="4.36,217,1228086000"; d="scan'208";a="18413824" Received: from nougat.ucs.ed.ac.uk ([129.215.13.205]) by mail2-smtp-roc.national.inria.fr with ESMTP; 14 Dec 2008 00:24:50 +0100 Received: from lmtp2.ucs.ed.ac.uk (lmtp2.ucs.ed.ac.uk [129.215.149.71]) by nougat.ucs.ed.ac.uk (8.13.8/8.13.4) with ESMTP id mBDNOhEf027936; Sat, 13 Dec 2008 23:24:46 GMT Received: from [192.168.1.65] (host81-154-223-74.range81-154.btcentralplus.com [81.154.223.74]) (authenticated bits=0) by lmtp2.ucs.ed.ac.uk (8.13.8/8.13.7) with ESMTP id mBDNObwm001659 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Sat, 13 Dec 2008 23:24:43 GMT Message-ID: <49444582.9070004@ed.ac.uk> Date: Sat, 13 Dec 2008 23:30:10 +0000 From: Jeremy Yallop User-Agent: Mozilla-Thunderbird 2.0.0.17 (X11/20081018) MIME-Version: 1.0 To: Christopher L Conway Cc: caml-list@inria.fr Subject: Re: [Caml-list] Immutable cyclic data structures via a References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Edinburgh-Scanned: at nougat.ucs.ed.ac.uk with MIMEDefang 2.60, Sophie, Sophos Anti-Virus, Clam AntiVirus X-Scanned-By: MIMEDefang 2.60 on 129.215.13.205 X-Scanned-By: MIMEDefang 2.52 on 129.215.149.71 Content-Disposition: inline X-Miltered: at discorde with ID 49444442.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 node:01 node:01 initializing:01 mutable:01 nodes:01 mutable:01 sig:01 struct:01 sig:01 val:01 val:01 struct:01 myers:98 beginners:01 Christopher L Conway wrote: > --- In ocaml_beginners@yahoogroups.com, Andrew Myers wrote: >> type node = edge list >> and edge = {from: node; to_: node} >> >> You'll have trouble initializing that data structure, though. Maybe >> better to add mutability somewhere, e.g. >> >> type node = {mutable outgoing: edge list} >> and edge = {from: node; to_: node} >> >> Then you can create all the nodes first and backpatch them with all the >> edges. > > This makes me wonder: if you add mutable fields to a type in order to > build a cyclic data structure, but you intend to use the data > structure immutably once it is built, is there any way to "freeze" the > value, producing an immutable cyclic structure? This is a common > pattern, similar to Bloch's Builder pattern for Java.[1] I believe that private types can do what you want. Private record types allow only read access, even to mutable fields, so if you have a type type node = private { mutable outgoing: edge list } then you can't update the "outgoing" field of any values of type node, even though it's declared mutable. You can then create a module which exports such a declaration in the signature: module Graph : sig type node = private { mutable outgoing : edge list } and edge = { from : node ; to_ : node } end = struct type node = { mutable outgoing : edge list } and edge = { from : node ; to_ : node } ... end Now you can make use of the mutability of the field within the implementation of the module (marked "...") but not outside the module: the module boundary acts as the "freeze" operation that converts mutable to immutable structures. Of course, this isn't particularly satisfactory, since you have to either anticipate all possible graph values when you write the module, or provide a clunky interface for constructing cyclic graphs. What you really want is to provide two versions of the graph type, both of which are visible to clients of the module, and an explicit "freeze" operation for converting mutable graphs to immutable graphs. I believe that the following code meets all your requirements, although it may be possible to make it more succinct. module Graph : sig module Mutable : sig type node = { mutable outgoing : edge list } and edge = { from : node ; to_ : node } end module Immutable : sig type node = private { mutable outgoing : edge list } and edge = { from : node ; to_ : node } end module Freeze : sig val node : Mutable.node -> Immutable.node val edge : Mutable.edge -> Immutable.edge end end = struct module Graph = struct type node = { mutable outgoing : edge list } and edge = { from : node ; to_ : node } end module Mutable = Graph module Immutable = Graph module Freeze = struct let node n = n let edge e = e end end Now you can, outside the module, create cyclic values using mutability: open Graph.Mutable let medge = { from = {outgoing = []}; to_ = {outgoing = []}; } let () = medge.from.outgoing <- [medge] let () = medge.to_ .outgoing <- [medge] and then freeze them so that they can no longer be updated. let iedge = Graph.Freeze.edge medge (Of course, you can still update the graph via the "medge" binding, but it's easy enough to prevent access to that, if necessary.) Hope this helps, Jeremy. -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336.