CODEWITHSUNDEEP
listhaskelltransposenested-listsdefinition
Kalo
Kalo

Reputation: 81

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

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

Upvotes: 2

Views: 871

Answers (2)

Marco_O
Marco_O

Reputation: 111

In case you want to use head and tail in the transposition of a list of lists, consider padding them so that you never run out of list items to map those functions to. Namely, you want to append a trail of zeroes (or some other item), like this:

[1,2,3]++[0,0..
[4,5]++[0,0,0..
[6,7,8,9]++[0..

so that when you use transposeWith 0 and arrive at:

[1,4,6]
[2,5,7]
[3,0,8]
[0,0,9]
[0,0,0]
...

you only need to takeWhile the lists are not a list with as many zeroes as the initial size of the list of lists. In other words, you get a rectangular one, and it works for an arbitrary size. Here's the implementation:

transposeWith m mss = takeWhile (/= [m | _ <- mss])
                                (map head (map (++ repeat m) mss) : 
                                transposeWith m (map tail (map (++ repeat m) mss)))

Upvotes: 0

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476388

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]]

So 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

Upvotes: 9

Related Questions