Immutable cyclic data structures via a

[Christopher L Conway <cconway@cs.nyu.edu>]

--- In ocaml_beginners@yahoogroups.com, Andrew Myers <andru@...> 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