[Haskell-beginners] Applicative functors and trees

[Darryn Reid]

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.