[Haskell-beginners] Applicative functors and trees

[Brent Yorgey]

On Mon, Mar 22, 2010 at 11:59:56AM +1030, Darryn Reid wrote:
> Hi,
>  
> 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 think there are actually lots of different Applicative instances for
Tree, just like there are (at least) two Applicative instances for
lists, one that "zips" the lists elementwise and one that takes all
possible combinations.  You can do something similar with trees;
Maciej's instance corresponds to "zipping" two trees together, but you
can also do something like combining the functions in the first tree
in every possible way with the values in the second tree, the
complicated part is figuring out how to put all these results back
together into a tree.

But at any rate, you *don't* need an Applicative instance in order to
define a Traversable instance.  Traversable instances follow a nice
regular pattern; they look exactly like Functor instances but with
normal application replaced by application in an Applicative context.
So, in your case:

  instance Traversable Tree where
    traverse f Empty = pure Empty
    traverse f (Leaf x) = Leaf <$> f x
    traverse f (Node l x r) = Node <$> traverse f l <*> f x <*> traverse f r

The thing to keep in mind is that the Applicative instance being used
here is NOT the one for Tree (which need not even have one), it is
whatever Applicative the caller of traverse is choosing to use as the
context of the traversal.  All the traverse implementation has to do
is apply f to every value in the tree from left to right.

-Brent