Introduction
Many resources discuss the formal definitions of Foldable
1 and Traversable
2.
For example:
- Foldable and Traversable3 on the Haskell Wiki.
- Sections 104 and 115 of the Typeclassopedia.
- Foldable/Traversable6 in Stephen Diehl's magnum opus.
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.
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