How does this transpose function work?

Question

I have this function given by my professor and I have no idea what is actually happening.

Here is the function that computes the transpose of an m-by-n matrix:

let rec transpose = function
| [] -> failwith "cannot transpose a 0-by-n matrix"
| []::xs -> [] 
| xs -> List.map List.head xs :: transpose (List.map List.tail xs)

Testing the function:

> transpose [[1;2;3];[4;5;6]];;
  val it : int list list = [[1; 4]; [2; 5]; [3; 6]]

I understand List.map, recursion and all that stuff. I just do not understand why/how this function works. Any clarifications will be much appreciated! Thanks!

Answer 1

Say we have a 3x3 matrix A.

let A = 
  [ [1;2;3]
    [4;5;6]
    [7;8;9] ]

= [ R1
    R2
    R3 ]

Now, let's analyse the transpose function.

let rec transpose = function
| [] -> failwith "cannot transpose a 0-by-n matrix"
| []::xs -> [] 
| xs -> List.map List.head xs :: transpose (List.map List.tail xs)

The first 2 cases catch the events where:

• the list is an empty list
• the list contains an empty list, meaning all inner lists have been processed

The code [1]

List.map List.head xs

maps the inner lists to their respective head elements

R1.Head ; R2.Head ; R3.Head
= 1 ; 4 ; 7
= C1

The code [2]

transpose (List.map List.tail xs)

(recursivly) transposes the tails of the beheaded lists. So on each recursion a column gets transposed into a row. Using the :: keyword these rows are then used to construct the resulting list.

transpose A
= C1 :: C2 :: C3 :: []
= [ C1
    C2
    C3 ]
= [ [1;4;7]
    [2;5;8]
    [3;6;9] ]