[Haskell-cafe] Tree Semantics and efficiency

Rouan van Dalen rvdalen at yahoo.co.uk
Wed Jun 17 10:15:43 EDT 2009

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



More information about the Haskell-Cafe mailing list