Understanding this matrix transposition function in Haskell

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 g开发者_运维知识库et 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?

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.

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

ghci is your friend:

*Main> :t map head
map head :: [[a]] -> [a]
*Main> :t map tail
map tail :: [[a]] -> [[a]]

Even if you don't understand map (a problem you'd want to correct quickly!), the types of these expressions tell much about how they work. The first is a single list taken from a list of lists, so let's feed a simple vector to it to see what happens.

You might want to write

*Main> map head [1,2,3]

but that fails to typecheck:

<interactive>:1:14:
    No instance for (Num [a])
      arising from the literal `3' at :1:14
    Possible fix: add an instance declaration for (Num [a])
    In the expression: 3
    In the second argument of `map', namely `[1, 2, 3]'
    In the expression: map head [1, 2, 3]

Remember, the argument's type is a list of lists, so

*Main> map head [[1,2,3]]
[1]

Getting a bit more complex

*Main> map head [[1,2,3],[4,5,6]]
[1,4]

Doing the same but with tail instead of head gives

*Main> map tail [[1,2,3],[4,5,6]]
[[2,3],[5,6]]

As you can see, the definition of transpose is repeatedly slicing off the first “row” with map head x and transposing the rest, which is map tail x.

These things are the same:

map head xxs
map (\xs -> head xs) xxs

It's lambda-expression, which means i return the head of xs for every xs Example:

   map head [[1,2,3],[4,5,6],[7,8,9]]
-> map (\xs -> head xs) [[1,2,3],[4,5,6],[7,8,9]]
-> [head [1,2,3], head [4,5,6], head [7,8,9]]
-> [1,4,7]

It's simple

By the way, this function doesn't work when given an input like [[1,2,3], [], [1,2]]. However, the transpose function from Data.List will accept this input, and return [[1,1], [2,2], [3]].

When we are calling the recursive transpose code, we need to get rid of the [].

In case you want to transpose rectangular arrays using head and tail, making sure that the number of columns is the same beforehand, then you can do the following:

rectangularTranspose :: [[a]] -> [[a]]
rectangularTranspose m = rectTrans m []
  where
    rectTrans [] a = a
    rectTrans ([]:xss) a = rectTrans xss a
    rectTrans ((x:xs):xss) a = rectTrans a ((x:map head xss): rectTrans (xs:map tail xss) a)

It works for square arrays and singletons too, obviously, but I don't see much use in this when the standard implementation gives you more options.

Alternatively, you could just define your own function. I found a simpler way to implement matrix transpose in Haskell using only list comprehension. It works for a generic m* n matrix with non-empty elements

transpose' :: [[a]] -> [[a]]
transpose' xss = chop nrows [xs !! (j-1) | i <- [1..ncols], j <- take nrows [i, i+ncols ..]] 
                where nrows = length  xss
                      ncols = length(head xss) 
                      xs = concat xss 

chop :: Int -> [a] -> [[a]]
chop _ [] = []
chop n xs = take n xs : chop n (drop n xs)