Help me to explain the F# Matrix transpose function

Question

There is a Matrix transpose function:

let rec transpose = function
    | (_::_)::_ as M -> List.map List.head M :: transpose (List.map List.tail M)
    | _ -> []

[[1; 2; 3]; [4; 5; 6]; [7; 8; 9]] |> transpose |> printfn "%A"

It works fine.
What does ( _ :: _ ) :: _ mean?
I don't understand the whole code!
Who can explain it?
Thank You!

I find the answer:
( _ :: _ ) :: _ is a pattern matching on value of type list of lists of ints

---

If i write:

let rec transpose (M:int list list) =
    match M with
    | hd::tl -> List.map List.head M :: transpose (List.map List.tail M)
    | _ -> []

It throw an runtime exception. Is there something wrong with hd?
Yes, it make something like [ [ ];[ ];[ ] ] when call List.tail, then it throws exception when call List.head!

---

Problem Solved!
Thank you all!

Answer 1

The function is not particularly readably written, which may be the reason for your confusion. The construct (_::_)::_ is a pattern matching on value of type list of lists of ints that says that the first case should be run when you get a non-empty list of non-empty lists.

The same thing can be written like this. This is more verbose, but it should be clear what is going on here:

let rec transpose matrix = 
  match matrix with   // matrix is a list<list<int>>
  | row::rows ->      // case when the list of rows is non-empty
    match row with    // rows is a list<int>
    | col::cols ->    // case when the row is non-empty
      // Take first elements from all rows of the matrix
      let first = List.map List.head matrix
      // Take remaining elements from all rows of the matrix
      // and then transpose the resulting matrix
      let rest = transpose (List.map List.tail matrix) 
      first :: rest
    | _ -> []
  | _ -> [] 

As you can see, we don't really need the values row, rows, col and cols. That's why the original implementation replaces these with _ (which ignores the value and only checkes that the list can be decomposed in the required way).

In the recursive case, we deconstruct the matrix like this:

[ [ x; y; y ];                               [ y; y ] 
  [ x; y; y ];   =>  [ x; x; x] :: transpose [ y; y ]
  [ x; y; y ] ]                              [ y; y ] 

I hope that the picture makes it more clear for you!