Why does Haskell's `transpose` function in Data.List not use `head` and `tail`?

user_11452237 0
Viewed 465

I've just spent some time working on a problem for which I needed to translate a list of lists a certain way. After successfully working through it I came up with this solution:

translate :: [[a]] -> [[a]]
translate ([]:xss) = []
translate xss      = (map head xss) : (translate $ map tail xss)

Very shortly afterwards, i realized that I was simply trying to transpose a matrix... I thought "I probably lost a lot of time trying to do this, as surely Haskell has a function in its standard libraries to do such a common operation." So I decided to check, and unsurprisingly I found that the Data.List module includes a transpose function.

But what was actually surprising to me was the way it was defined:

transpose               :: [[a]] -> [[a]]
transpose []             = []
transpose ([]   : xss)   = transpose xss
transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss])

It uses list comprehensions instead of head and tail, which I thought was interesting but could not figure out why it did so.

Is there a reason why it is better to use list comprehension instead of the pre-defined head and tail functions (with map), the way that I did with my function? Is it something to do with the efficiency of the code?

I am not necessarily new to Haskell, but I am not an expert either. That being said, more technical answers and explanations would also be greatly appreciated as I am hoping to learn more about the intricacies of the language going forward (and even if I don't understand the reason now I will know what I have to research).

nested-lists transpose definition list haskell
1 Answers

For empty lists, functions like head and tail will error. Note that if you write:

[h | (h:_) <- xss]

then this is not equivalent to map head xss. Indeed, the above list comprehension is equivalent to:

let ok (h:_) = pure h
    ok _ = fail "…"
in xss >>= ok

So in case the pattern matching fails, then we return a fail "" value. For a list this is the empty list:

Prelude> fail "" :: [Int]
[]

This is important for non-rectangular lists that we want to transpose, for example:

Prelude Data.List> transpose [[1,4,2,5],[1,3], [1,9,5,8]]
[[1,1,1],[4,3,9],[2,5],[5,8]]

Si it will transform:

[ 1 4 2 5]
[ 1 3 ]
[ 1 9 5 8]

to:

[1 1 1]
[4 3 9]
[2 5]
[5 8]

Whereas if one uses head and tail eventually when it aims to calculate the head and tail in the third row, it will crash on the [1,3] list:

Prelude Data.List> transpose' [[1,4,2,5],[1,3], [1,9,5,8]]
[[1,1,1],[4,3,9],[2,*** Exception: Prelude.head: empty list
user_675790
Related