[Haskell-cafe] Growing Trees

[Sebastian Sylvan]

On 9/22/05, Tom Hawkins <tom at confluent.org> wrote:
> I'm porting an ML program to Haskell, but am having difficulty with
> particular data structure: a tree where each node has references to the
> children as well as the parent...
>
> 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.  There is also the add coding complexity
> of threading the tree through various functions to simulate state.
>
> What are my [monadic] options?
>

You can't do trees with mutable references in Haskell without doing it
a state monad (ST, or IO, basically).

However, it is possible to use laziness in order to have bidirectional
"links", but doing so is kinda tedious (you can't pattern match on one
constructor, you need to pattern match against two "levels" so you can
construct the parent and the child at the same time).

Here's a binary tree I threw together just now (not thouroughly
tested!) where each node has a link to its parent.

Note how laziness is used to make the parent refer to the child and
the child refer to the parent.
Some code could be saved by stating that a Root is just a Node with a
Nil parent, but I didn't want to complicate it too much.

-----------

data TreeParent a = Root a (TreeParent a) (TreeParent a)
                                     | Node a (TreeParent a)
(TreeParent a) (TreeParent a)
                                     | Nil


insert :: Ord a => TreeParent a -> a -> TreeParent a

insert (Root a Nil Nil) k = parent
    where parent | k < a =  Root a child Nil
                             | otherwise = Root a Nil child
                child = Node k parent Nil Nil

insert (Root a Nil t2) k
    | k < a = parent
    | otherwise = Root a Nil (insert t2 k)
    where parent = Root a child t2
               child = Node k parent Nil Nil

insert (Root a t1 Nil ) k
    | k < a = Root a (insert t1 k) Nil
    | otherwise = parent
    where parent = Root a t1 child
                child = Node k parent Nil Nil

insert (Root a t1 t2) k
    | k < a = Root a (insert t1 k) t2
    | otherwise = Root a t1 (insert t2 k)

insert (Node a p Nil Nil) k = parent
    where parent | k < a =  Node a p child Nil
                             | otherwise = Node a p Nil child
                child = Node k parent Nil Nil

insert (Node a p Nil t2) k
    | k < a = parent
    | otherwise = Node a p Nil (insert t2 k)
    where parent = Node a p child t2
                child = Node k parent Nil Nil

insert (Node a p t1 Nil ) k
    | k < a = Node a p (insert t1 k) Nil
    | otherwise = parent
    where parent = Node a p t1 child
               child = Node k parent Nil Nil

insert (Node a p t1 t2) k  | k < a = Node a p (insert t1 k) t2
                                            | otherwise = Node a p t1
(insert t2 k)

insert Nil k = Root k Nil Nil


toList Nil = []
toList (Node a _ t1 t2) = toList t1 ++ [a] ++ toList t2
toList (Root a t1 t2) = toList t1 ++ [a] ++ toList t2

-----------


/S
--
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862