[Haskell-cafe] Growing Trees

[Ben Rudiak-Gould]

[Previously sent only to the OP -- oops]

Tom Hawkins wrote:
> data Tree a
>   = TreeRoot { stuff    :: a
>              , children :: [Tree]
>              }
>   | TreeNode { stuff    :: a
>              , parent   :: Tree
>              , children :: [Tree]
>              }
> 
> But because of these bidirectional links, every time I add a node I must 
> reconstructing the entire tree.

If you don't want to use IORefs or STRefs, you could try The Zipper:

     http://www.haskell.org/hawiki/TheZipper

or you could represent the tree as

   type Tree a = Data.Map.Map Int (Node a)

   data Node a = TreeRoot { stuff :: a, children :: [Int] }
               | TreeNode { stuff :: a, parent :: Int, children :: [Int] }

-- Ben