Haskell Language Traversable Transposing a list of lists
Example
Noting that zip transposes a tuple of lists into a list of tuples,
ghci> uncurry zip ([1,2],[3,4])
[(1,3), (2,4)]
and the similarity between the types of transpose and sequenceA,
-- transpose exchanges the inner list with the outer list
-- +---+-->--+-+
-- | | | |
transpose :: [[a]] -> [[a]]
-- | | | |
-- +-+-->--+---+
-- sequenceA exchanges the inner Applicative with the outer Traversable
-- +------>------+
-- | |
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
-- | |
-- +--->---+
the idea is to use []'s Traversable and Applicative structure to deploy sequenceA as a sort of n-ary zip, zipping together all the inner lists together pointwise.
[]'s default "prioritised choice" Applicative instance is not appropriate for our use - we need a "zippy" Applicative. For this we use the ZipList newtype, found in Control.Applicative.
newtype ZipList a = ZipList { getZipList :: [a] }
instance Applicative ZipList where
pure x = ZipList (repeat x)
ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)
Now we get transpose for free, by traversing in the ZipList Applicative.
transpose :: [[a]] -> [[a]]
transpose = getZipList . traverse ZipList
ghci> let myMatrix = [[1,2,3],[4,5,6],[7,8,9]]
ghci> transpose myMatrix
[[1,4,7],[2,5,8],[3,6,9]]
