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