2011/7/23 Александр :

Hello,

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?

i try:

instance Monad Tree where     return x = Node x Empty Empty     Empty >>= f = Empty     (Node x Empty Empty) >>= f = f x

1) Do you really need a Monad instance for this? 2) One possibility is just have it being (Node x _ _) >>= f = f x -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

2011/7/23 Александр :

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.

On Jul 23, 2011, at 7:31 AM, Александр wrote:

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?

Like David said, you'll need a sensible way to merge 2 trees. As we have no Ord a, the only sensible thing to do is to append them, so the order of the elements is maintained and then the Monad instance will work like the list monad. First we'll have to agree on the ordering, I'll assume: toList :: Tree a -> [a] toList Empty = [] toList (Node a l r) = toList l ++ [a] ++ toList r Next is the append function. Let's make a Monoid instance for extra fun. (You'll need to import Data.Monoid) instance Monoid (Tree a) where mempty = Empty mappend Empty x = x mappend (Node a l r) x = Node a l (mappend r x) This will generate unbalanced trees, but it'll have to do. Now the Monad instance: instance Monad Tree where return a = Node a Empty Empty Empty >>= _ = Empty Node a l r >>= f = case f a of Empty -> (l >>= f) `mappend` (r >>= f) Node b lb rb -> Node b ((l >>= f) `mappend` lb) (rb `mappend` (r >>= f)) Let's see if this indeed behaves like the list monad. fromList :: [a] -> Tree a fromList [] = Empty fromList xs = Node a (fromList l) (fromList r) where (l, a:r) = splitAt (length xs `div` 2) xs

toList $ fromList [10,20,30] >>= (\x -> fromList [x - 1, x, x + 1]) [9,10,11,19,20,21,29,30,31]

It works! -- Sjoerd Visscher