[Haskell-beginners] Applicative Functors: Rose Trees with an alternate behavior

[Travis Erdman]

> 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