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.7 required=5.0 tests=AWL,SPF_FAIL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id A251EBB84 for ; Sat, 13 Dec 2008 22:45:24 +0100 (CET) X-IronPort-AV: E=Sophos;i="4.36,217,1228086000"; d="scan'208";a="32612870" Received: from concorde.inria.fr ([192.93.2.39]) by mail4-smtp-sop.national.inria.fr with ESMTP; 13 Dec 2008 22:45:24 +0100 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id mBDLjNgN003664 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Sat, 13 Dec 2008 22:45:24 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ak8BAKu7Q0lQW+UCe2dsb2JhbACTUQEBFiIEsAmFWoUogn0 X-IronPort-AV: E=Sophos;i="4.36,217,1228086000"; d="scan'208";a="21226527" Received: from main.gmane.org (HELO ciao.gmane.org) ([80.91.229.2]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/AES256-SHA; 13 Dec 2008 22:45:23 +0100 Received: from list by ciao.gmane.org with local (Exim 4.43) id 1LBcIb-0004VX-EO for caml-list@inria.fr; Sat, 13 Dec 2008 21:45:21 +0000 Received: from cpe-69-203-209-238.nyc.res.rr.com ([69.203.209.238]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sat, 13 Dec 2008 21:45:21 +0000 Received: from cconway by cpe-69-203-209-238.nyc.res.rr.com with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sat, 13 Dec 2008 21:45:21 +0000 X-Injected-Via-Gmane: http://gmane.org/ To: caml-list@inria.fr From: Christopher L Conway Subject: Immutable cyclic data structures via a Date: Sat, 13 Dec 2008 21:45:07 +0000 (UTC) Message-ID: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Complaints-To: usenet@ger.gmane.org X-Gmane-NNTP-Posting-Host: main.gmane.org User-Agent: Loom/3.14 (http://gmane.org/) X-Loom-IP: 69.203.209.238 (Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.0.4) Gecko/2008111318 Ubuntu/8.10 (intrepid) Firefox/3.0.4) Sender: news X-Miltered: at concorde with ID 49442CF3.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 beginner's:01 node:01 node:01 initializing:01 mutable:01 nodes:01 mutable:01 val:01 ocaml:01 ugliness:01 haskell:01 haskell:01 myers:98 beginners:01 --- In ocaml_beginners@yahoogroups.com, Andrew Myers wrote: > [Note from Chris: I'm reposting this from the beginner's list, because I'm interested in an answer and more likely to get it here... A declaration of a graph data structure might be:] > > 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] You might have an operation, call it "unmute", that changes the type of the structure. There would need to be a corresponding type-level operation, call it "UNMUTE", that strips the "mutable" qualifier from mutable fields. E.g., val unmute : 'a -> UNMUTE('a) and UNMUTE(node) = { outgoing : edge list } for node as defined above. I'm pretty confident this isn't possible in plain-vanilla OCaml. You can do something similar (at a high cost in ugliness) using a variation of "Tying the Knot" a la Haskell.[2] Is anybody aware of a language extension that does this, or a similar feature in another language? Regards, Chris [1]: http://www.screaming-penguin.com/node/7598 "The essence of the enhanced builder pattern in Java" [2]: http://www.haskell.org/haskellwiki/Tying_the_Knot