CODEWITHSUNDEEP
listhaskellnested-lists
Brendan Langfield
Brendan Langfield

Reputation: 585

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

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?

Upvotes: 4

Views: 180

Answers (3)

Daniel Wagner
Daniel Wagner

Reputation: 153172

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!)

Upvotes: 8

chi
chi

Reputation: 116174

The type

transpose :: [[a]] -> [[a]]

makes transpose take a list-of-lists of a. Here a is an arbitrary type, so transpose does not (and can not) inspect its input beyond two levels of lists.

Hence, the cases you posted are "seen" by transpose as follows:

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

Now, it's easier to understand. As user2357112 already explained in their answer, the input [] is a 0*? matrix, [[]] is a 1*0 matrix, and [[something]] is a 1*1 matrix.

Upvotes: 7

user2357112
user2357112

Reputation: 281748

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.

Upvotes: 10

Related Questions