## Introduction

Many resources discuss the formal definitions of `Foldable`

^{1} and `Traversable`

^{2}.

For example:

- Foldable and Traversable
^{3}on the Haskell Wiki. - Sections 10
^{4}and 11^{5}of the Typeclassopedia. - Foldable/Traversable
^{6}in Stephen Diehl's*magnum opus*.

Recently though, I was struck by the succinct clarity of Michael Burge’s comment in the Haskell Cafe^{7}:

There’s Foldable for ‘things that can be converted to lists’, or Traversable for ‘things that can be converted to lists underneath a Functor’.

With this in mind, let’s think about transposing a matrix represented as a list-of-lists.

## A list of lists

Although it’s not what you’d choose if you care about performance, you can represent a matrix as a list-of-lists. If the element type is `a`

then the list has type `[a]`

, and the matrix has type `[[a]]`

.

From Michael Burge’s comment, it’s clear that the matrix must be an instance of `Traversable`

if we choose the ‘Functor above the list’ to be another list.

For clarity let’s invent a second kind of list, represented by `⟦a⟧`

rather than `[a]`

.

Then our matrix might have type `⟦[a]⟧`

where `⟦⟧`

represents rows and `[]`

represents columns.

## sequenceA

One of the key functions in `Traversable`

is `sequenceA`

:

```
ghci> :t sequenceA
sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)
```

If we specialize this for our list-of-lists:

`sequenceA :: ⟦[a]⟧ -> [⟦a⟧]`

That certainly looks like a transpose, but is it ?

```
ghci> sequenceA [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
```

Sadly not! The snag is that we’re forming the Cartesian product of the lists, rather than forming new lists by matching up the n^{th} elements of the old ones.

## ZipList to the rescue

Recall that the Cartesian product comes from the monad instance for lists, but you can make a different but perfectly good Applicative instance called `ZipList`

. Here’s an illustration of the difference:

```
ghci> (,) <$> ZipList [1,2] <*> ZipList [3,4]
ZipList {getZipList = [(1,3),(2,4)]}
ghci> (,) <$> [1,2] <*> [3,4]
[(1,3),(1,4),(2,3),(2,4)]
```

This looks much better, and indeed is the solution to our problem:

```
ghci> getZipList $ sequenceA $ map ZipList [[1,2,3],[4,5,6]]
[[1,4],[2,5],[3,6]]
```

or, more generally:

`transpose = getZipList . sequenceA . map ZipList`

Intuitively:

- turn the list of columns into a list of
`ZipLists`

; - make a new
`ZipList`

by making a list of all the 1^{st}elements, then a list of all the 2^{nd}elements and so on; - turn that
`ZipList`

back into a normal list.

All this is in McBride and Paterson’s original paper^{8}, so you should read that if you’re interested.

## References

- 1. https://hackage.haskell.org/package/base/docs/Data-Foldable.html
- 2. https://hackage.haskell.org/package/base/docs/Data-Traversable.html
- 3. https://wiki.haskell.org/Foldable_and_Traversable
- 4. https://wiki.haskell.org/Typeclassopedia#Foldable
- 5. https://wiki.haskell.org/Typeclassopedia#Traversable
- 6. http://dev.stephendiehl.com/hask/#foldable-traversable
- 7. https://mail.haskell.org/pipermail/haskell-cafe/2016-April/123754.html
- 8. http://www.staff.city.ac.uk/~ross/papers/Applicative.pdf