On Mon, 2010-03-22 at 11:59 +1030, Darryn Reid wrote:
Where I'm stuck is with Applicative: class (Functor f) => Applicative f where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b
I understand that pure lifts a value into the applicative functor, so this one is easy: pure = Leaf but I cannot see what <*> should look like. I know that <*> is essentially application ($) lifted into the functor, so if the functor were also a monad then <*> would be liftM2 ($), I suppose. But I want a "direct" implementation, without monads floating about, but I cannot see what to do.
Hmm. When I played with trees I've done: data Tree a = Leaf | Node (Tree a) a (Tree a) instance Applicative Tree where pure x = let t = Node t x t in t -- if you prefer Node (pure x) x (pure x) -- or fix (\t -> Node t x t) Leaf <*> _ = Leaf _ <*> Leaf = Leaf (Node l f r) <*> (Node l' v r') = Node (l <*> l') (f v) (r <*> r') So maybe: instance Applicative Tree where pure x = let t = Node t x t in t -- if you prefer Node (pure x) x (pure x) Empty <*> _ = Empty _ <*> Empty = Empty (Leaf f) <*> (Leaf v) = Leaf (f v) (Leaf f) <*> (Node _ v _) = Leaf (f v) (Node _ f _) <*> (Leaf v) = Lead (f v) (Node l f r) <*> (Node l' v r') = Node (l <*> l') (f v) (r <*> r') Both have unpleasant property of function returning infinite tree. Regards PS. Why do you need Leaf? How does Leaf x differ from (Node Empty x Empty)?