Understanding this matrix transposition function in Haskell

Question

This matrix transposition function works, but I'm trying to understand its step by step execurtion and I don't get it.

    transpose:: [[a]]->[[a]]     transpose ([]:_) = []     transpose x = (map head x) : transpose (map tail x) 

with

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

it returns:

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

I don't get how the concatenation operator is working with map. It is concatenating each head of x in the same function call? How?

is this

(map head x) 

creating a list of the head elements of each list?

Answer 1

Let's look at what the function does for your example input:

transpose [[1,2,3],[4,5,6],[7,8,9]] <=> (map head [[1,2,3],[4,5,6],[7,8,9]]) : (transpose (map tail [[1,2,3],[4,5,6],[7,8,9]])) <=> [1,4,7] : (transpose [[2,3],[5,6],[8,9]]) <=> [1,4,7] : (map head [[2,3],[5,6],[8,9]]) : (transpose (map tail [[2,3],[5,6],[8,9]])) <=> [1,4,7] : [2,5,8] : (transpose [[3],[6],[9]]) <=> [1,4,7] : [2,5,8] : (map head [[3],[6],[9]]) : (transpose (map tail [[3],[6],[9]])) <=> [1,4,7] : [2,5,8] : [3, 6, 9] : (transpose [[], [], []]) <=> [1,4,7] : [2,5,8] : [3, 6, 9] : [] -- because transpose ([]:_) = [] <=> [[1,4,7],[2,5,8],[3,6,9]] 

Note that the order in which I chose to reduce the terms, is not the same as the evaluation order haskell will use, but that does not change the result.

Edit: In response to your edited question:

is this

(map head x) 

creating a list of the head elements of each list?

Yes, it is.

Answer 2

The cons operator : attach an object of type a to a list of type [a]. In

(map head x) : transpose (map tail x) 

The LHS is a list (a = [b]), while the RHS is a list of list ([a] = [[b]]), so such a construction is valid. The result is

[x,y,z,...] : [[a,b,...],[d,e,...],...] = [[x,y,z,...], [a,b,...],[d,e,...],...] 

---

In your case, map head x and map tail x splits the matrix

x = [[1,2,3],[4,5,6],[7,8,9]] 

into

map head x = [1,4,7] map tail x = [[2,3],[5,6],[8,9]] 

(and yes, map head x is a list of the head elements of each list.) The 2nd part is transposed (for detail steps see @sepp2k's answer) to form

transpose (map tail x) = [[2,5,8],[3,6,9]] 

so cons-ing [1,4,7] to this gives

map head x : transpose (map tail x) =  [1,4,7] : [[2,5,8],[3,6,9]]                                     = [[1,4,7] ,  [2,5,8],[3,6,9]]