Why is `tranpose [[]] == []` in Haskell?

Question

Consider the following?

ghci> transpose []
[]
ghci> transpose [[]]
[]
ghci> transpose [[[]]]
[[[]]]
ghci> transpose [[[[]]]]
[[[[]]]]
ghci> transpose [[[[[]]]]]
[[[[[]]]]]
ghci> transpose [[[[[[]]]]]]
[[[[[[]]]]]]

One of these things is not like the other :p

It is very strange to me to see something so seemingly unelegant in base, but I suppose there's some excellent algebraic or theoretical reason why they chose to have transpose [[]] == []. Can anyone shed some light on this?

Answer 1

transpose swaps rows and columns.

[] has 0 rows and a not-really-well-defined number of columns that the function just treats as 0. Swapping 0 rows with 0 columns doesn't change anything.

[[[]]] and beyond each have 1 row and 1 column. Swapping 1 row with 1 column doesn't change anything either.

[[]] has 1 row and 0 columns. Swapping 1 row and 0 columns produces an output with 0 rows: an empty list.

Answer 2

I like the consideration mentioned in the other answers when thinking of [[a]] as a matrix. But I do object slightly on the grounds that not all [[a]] really are matrices; it is quite often useful to have "jagged" nested lists, and transpose can still be sensible and useful on them. So I'd like to give some arguments that do not assume rectangular-ness. I have two.

First, suppose we lived in an alternative universe where transpose [[]] = [[]]. Now, what should transpose [[], []] do? There's not really a good way to reflect in the output that there were two empty lists in the input. So let's try choosing transpose [[], []] = [[]] again. But now we have an alternative broken pattern:

> transpose [[], [], []]
[[]]
> transpose [[], []]
[[]]
> transpose [[]]
[[]]
> transpose []
[] -- whoops, not [[]] like the pattern would suggest

If we make all the changes described above and change to transpose [] = [[]] so that this pattern works, then your original pattern is broken again.

> transpose [[[[]]]]
[[[[]]]]
> transpose [[[]]]
[[[]]]
> transpose [[]]
[[]]
> transpose []
[[]] -- whoops, not [] like the pattern would suggest

It seems it's just not possible to have a definition of transpose that makes all the patterns you might wish for work out.

Second, the current definition of transpose does have some nice algebraic properties. One such is this:

length' (transpose xs) = foldMap length' xs

Here length' is just like length, but returns an unsigned number whose Monoid instance uses mappend = max; mempty = 0. This property forces transpose [[]] = [], because

length' (transpose [[]]) = foldMap length' [[]]
                         = fold [length' []]
                         = fold [0]
                         = 0

and the only way to get length' foo = 0 is foo = [].

(This second argument is very, very similar to the one given in the other answers, though it's stated in very different language!)