Introduction

Many resources discuss the formal definitions of Foldable1 and Traversable2.

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:

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