## Introduction

Many resources discuss the formal definitions of `Foldable`1 and `Traversable`2.

For example:

Recently though, I was struck by the succinct clarity of Michael Burge’s comment in the Haskell Cafe7:

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 nth 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 1st elements, then a list of all the 2nd elements and so on;
• turn that `ZipList` back into a normal list.

All this is in McBride and Paterson’s original paper8, so you should read that if you’re interested.