The correct implementation of pure looks like this:
pure x = Node x (repeat (pure x))
(Hooray for lazy infinite data structures!) With this definition the standard sequenceA works just fine.
Ha, I would never have arrived at that solution in a million years on my own, but now that you show me, it makes perfect sense! Following the discussion of ZipLists from http://learnyouahaskell.com/functors-applicative-functors-and-monoids, my initial solution attempt was pure x = Node x (repeat x) but that doesn't even compile. I had suspected that I needed to make the pure tree "go down", but I couldn't see how to do it. OK, some follow-on questions if I may ... sequenceA [Tree a] now returns Tree [a], as indicated. Now, I'd also like sequenceA Tree [a] to return [Tree a]. To do that, I need to make Tree an instance of Traversable and, hence, Foldable. Here's my stab at doing that ... instance Foldable Tree where foldMap f (Node cargo subtrees) = f cargo `mappend` foldMap (foldMap f) subtrees instance Traversable Tree where traverse f (Node cargo subtrees) = Node <$> f cargo <*> traverse (traverse f) subtrees The Foldable code appears to be correct; at least, I can the fold the trees. "Foldable" also allows the toList Tree a to work as expected. Given that, I don't really "get" Traversable, and the code here is just my best guess as to what it should be. But, I think it must not be correct, because sequenceA Tree [a] is not returning what I think it should be returning (ie [Tree a]). Aside from this, what other things can I do with a Traversable Tree? My intuition suggests I might be able to do Scan's on a tree, say calculate a cumulative sums Tree from root to leaves (or vice versa). But I've no idea how to implement that using it's "Traversability". As of now, I have implemented this up-and-down scanning thusly ... treeScanDown :: (a -> b -> a) -> a -> Tree b -> Tree a treeScanDown f x (Node y subtrees) = Node g (fmap (treeScanDown f g) subtrees) where g = f x y treeScanUp :: (a -> [a] -> a) -> Tree a -> Tree a treeScanUp f (Node x []) = Node x [] treeScanUp f (Node x subtrees) = Node (f x (fmap fromNode g)) g where g = fmap (treeScanUp f) subtrees thanks again, travis