listhaskellnested-lists

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?


Solution

  • 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.