[Haskell-cafe] Tree Semantics and efficiency

[Miguel Mitrofanov]

You can use the standart "tying the knot"-technique. For example:

data Tree = TreeNode String (Maybe Tree) [Tree] -- what's the parent of the root node?

test :: Tree
test =
    let parent = TreeNode "I'm parent" Nothing [child1, child2]
        child1 = TreeNode "I'm child1" (Just parent) []
        child2 = TreeNode "I'm child2" (Just parent) []
    in parent

But there are other possibilities worth considering. Zippers, for example, would be likely useful.

IORefs are most certainly an overkill.

Rouan van Dalen wrote on 17.06.2009 18:15:
> 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.
> 
> 
> 
>       
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>