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

Travis Erdman traviserdman at yahoo.com
Tue Aug 10 15:08:01 EDT 2010

```> 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
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

```