[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
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
More information about the Beginners
mailing list