How to create mutually referencing data structures in Haskell?

Question

I've exploited the fact that when the JVM creates an object (immutable or not), its pointer is created before its fields are initialized.

That allows me to create something like this:

class BackRefdNode(val parent:Option[BackRefdNode],
node:ClassicNode){
  val children=node.children.map{c=> 
    new BackRefdNode(Some(this), c)
}

That's not the case (as far as I know) with Haskell, and if that's the case anyway, Haskell doesn't give me the tools to exploit that (gives me no reference to "this").

So I'm wondering, how do I achieve that in Haskell?

I thought that maybe th fix function could do the trick, but that would not actually give me a "this" reference, but a reference to a thunk that when calculated, would have, theoretically, the same structure as the created BackRefdNode

Answer 1

Haskell actually goes one step further here. It is lazily evaluated, which means you can get a reference to anything before it is initialised, not just objects with fields. Using the data types

data ClassicNode = ClassicNode { children :: [ClassicNode] }
data BackRefdNode = BackRefdNode { parent :: Maybe BackRefdNode, children :: [BackRefdNode] }

you can create a function

backRefdNode :: Maybe BackRefdNode -> ClassicNode -> BackRefdNode
backRefdNode parent node = let result = BackRefdNode parent (backRefdNode result <$> children node)
                           in result

Notice how result is referenced in the expression that initialises result itself. This works perfectly fine and efficiently shares the tree objects with circular references amongst them.

What will be harder than in Scala is unraveling this data structure, as there is no reference equality in Haskell. The invariant that every child of a BackRefdNode has it as its parent cannot be tested, it must be proven from the construction.