Hi,
I'm playing around with Functors in Haskell with the aim of
understanding more structured functors, particularly applicative
functors and traversable and foldable. I'm using the standard binary
tree type to play around with this, as follows:
data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
I think I understand Functor fine:
instance Functor Tree where
fmap f Empty = Empty
fmap f (Leaf x) = Leaf (f x)
fmap f (Node l x r) = Branch (fmap f l) (f x) (fmap f r)
(with (<$>) being a synonym for fmap). This satisfies the laws for
Functor (I'll omit details). Likewise, I think I'm fine with Foldable,
for Tree a over any monoid a:
instance Foldable Tree
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node l x r) = foldMap f l `mappend` f x `mappend`
foldMap f r
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.
I think then I would be able to define an instance for traversable as
something like this:
instance Traversable Tree
traverse f Empty = pure Empty
traverse f (Leaf x) = Leaf `fmap` f x
traverse f (Node l x r) = Node `fmap` traverse f (l <*> f x <*>
traverse f r)
(I think that <*> must be associative).
Can anyone advise what <*> should look like, please? Thanks in advance
for your help.
Darryn.
