Help me to explain the F# Matrix transpose function

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!

Leave a Comment