[Haskell-cafe] Tree Semantics and efficiency

[Rouan van Dalen]

Hi everyone.

I would like to confirm the following semantics.

I want a tree which can be traversed both downwards and upwards.
To do this i need to store the following for each node:

o) a reference to the parent node (so we can traverse up the tree).  This must be a reference as i dont want to copy the parent node each time)
o) a list of child nodes that belong to this node.

It is important to store only a reference to the parent and not a copy of the entire parent for efficiency.

How would one write this in Haskell so that it has the above mentioned semantics.
Or does GHC do that automatically for me so I don't need to do it explicitly?

I am thinking of writing something like this (naive implementation) :

     Tree = TreeNode String Tree [Tree]  -- TreeNode <data> <ParentReference> <ChildNodes>

OR (implementation using IORef for parentNode reference)

                Tree = TreeNode String (IORef Tree) [Tree]  -- TreeNode <data> <ParentReference> <ChildNodes>


Thanks in advance

Rouan.