Functors made for walking
instance Traversable Tree where traverse f t = case t of Leaf x -> Leaf <$> f x Branch tl tr -> Branch <$> traverse f tl <*> traverse f tr
transpose :: [[a]] -> [[a]] transpose = getZipList . traverse ZipList
Note that this
transpose behaves differently from the one in Data.List. That one will happily assemble columns of unequal length when given rows of unequal size, while our version cuts off extra elements. Neither solution is a very good one, but then nested lists are not a good representation for matrices in first place.
traverse mappend :: (Traversable t, Monoid b) => t b -> b -> t b
traverse mappend t is a
(Traversable t, Monoid b) => b -> t b function which monoidally appends its argument to all of the values in
t. The relevant
Applicative instance is the one for functions.
This is the type of
mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
With a couple flips, the type becomes...
(b -> (a -> (a, c))) -> t b -> (a -> (a, t c))
... which is equivalent to:
(b -> State a c) -> t b -> State a (t c)
That strongly suggests we can write
mapAccumL as a traversal with the
State applicative functor. One important issue to consider is how the applicative instance of
State sequences effects (for
State is not commutative). Since we know that instances in the libraries sequence from left to right, we are good to go (otherwise, we would have to use Control.Applicative.Backwards to avoid ending up with
-- Using a different name because of the flips. mapAccumLS :: (b -> State a c) -> t b -> State a (t c) mapAccumLS step t = traverse step t -- i.e. mapAccumLS = traverse
.. and that's it. All that is needed is undoing the flips and adding the
mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) mapAccumL step z t = runState (traverse (state . flip step) t) z
That is just like the actual implementation in Data.Traversable. The only difference is that
Data.Traversable uses an internal implementation of
State to avoid importing
Control.Monad.Trans.State (actually two implementations, thanks to the sequencing of effects issue).