## Functors made for walking

edit1.

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

edit
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).