[Haskell-cafe] Monad for binary tree data structure

[Felipe Almeida Lessa]

2011/7/23 Александр <kommunist1917 at mail.ru>:
> I built binary tree with:
>
> data Tree a = Empty
>               | Node a (Tree a) (Tree a)
>               deriving (Eq, Ord, Read, Show)
> How can i make Monad type class instance for this tree? And can i make it on
> not?

If you had a monad for Tree a, then you'd have

  join :: Tree (Tree a) -> Tree a
  join x = x >>= id

It is non-obvious for me how such function would behave.  (I'm not
saying it's impossible.)

However, you may try with a different binary tree, having data only on
the leafs:

  data Tree a = Leaf a | Node (Tree a) (Tree a)

It's pretty easy to define it as a monad:

  instance Monad Tree where
    return = Leaf
    Leaf a >>= f = f a
    Node l r >>= f = Node (l >>= f) (r >>>= r)

Then you get basically:

  join :: Tree (Tree a) -> Tree a
  join (Left t) = t
  join (Node l r) = Node (join l) (join r)

In other words, join just glues the trees on the leafs to the tree
itself.  It's kinda straightforward.

Cheers,

-- 
Felipe.