Haskell/Solutions/Traversable

Functors made for walking 1. 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 Interpretations of Traversable 1. transpose :: [[a]] -> [[a]] transpose = getZipList . traverse ZipList Note that this transpose behaves differently from the one in base latest 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. 2. 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. 3. This is the type of mapAccumL: 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 transformers latest Control Applicative Backwards to avoid ending up with mapAccumR). -- 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 state/runState boilerplate. 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 base latest 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).