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!