Haskell/Solutions/Traversable

← Back to 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 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 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 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).