Re: [Caml-list] Immutable cyclic data structures via a

[Jeremy Yallop <jeremy.yallop@ed.ac.uk>]

Christopher L Conway wrote:
> --- In ocaml_beginners@yahoogroups.com, Andrew Myers <andru@...> 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.