#2 .. this is probably correct: {-# LANGUAGE InstanceSigs #-} module TreeApp where import Debug.Trace import Data.Char data Tree a = Node a [Tree a] deriving (Show) instance Functor Tree where fmap::(a -> b) -> Tree a -> Tree b fmap f (Node x l0) = Node (f x) (fmap f <$> l0) instance Applicative Tree where pure::a -> Tree a pure a = Node a [] (<*>)::Tree (a -> b) -> Tree a -> Tree b (<*>) (Node f []) tra = f <$> tra (<*>) tab@(Node f tf0) (Node x l0) = Node (f x) l1 where l1 = [fu <*> a | fu <- tf0 , a <- l0] instance Monad Tree where return::a -> Tree a return a = pure a (>>=)::Tree a -> (a -> Tree b) -> Tree b (>>=) (Node x []) amb = amb x (>>=) (Node x l0) amb = Node b (m1 <$> l0) where (Node b _) = amb x m1 ta = ta >>= amb f1::Char->Int f1 = digitToInt mb::Char->Tree Int mb c = f1 <$> (pure c) main::Char -> Char -> IO () main a b = print $ tc4 >>= mb where tc1 = Node a [Node b []] ti2 = f1 <$> tc1 ta3 = (Node f1 []) <*> tc1 tc4 = Node b [tc1]