If we are to represent a row of a matrix as a list of numbers, then a matrix can naturally be represented as a list of lists of numbers.

The transpose of a matrix $\mathbf{A}$ is a new matrix denoted $\mathbf{A^{T}}$. The traditional mathematical definition of $\mathbf{A^{T}}$ is expressed as saying the $i$ th row, $j$ th column element of $\mathbf{A^{T}}$ is the $j$ th row, $i$ th column element of $\mathbf{A}$:

As definitions go, this isn't terribly helpful in
explaining *how* to compute a transpose. A better
equivalent definition for the functional programmer is : the
matrix obtained by writing the columns of $\mathbf{A}$ as the
rows of $\mathbf{A^{T}}$.

An elegant program for computing a transpose follows from a direct translation of that last definition.

```
let rec transpose (ls : 'a list list) : 'a list list =
match ls with
| [] | [] :: _ -> []
| ls -> List.map (List.hd) ls :: transpose (List.map (List.tl) ls)
```

It is not at all hard to understand how the program works when you've seen an example:

```
transpose [[1; 2]; [3; 4;]; [5; 6]]
= [1; 3; 5] :: transpose [[2]; [4;]; [6]]
= [1; 3; 5] :: [2; 4; 6] :: transpose [[]; []; []]
= [1; 3; 5] :: [2; 4; 6] :: []
= [[1; 3; 5]; [2; 4; 6]]
```

Being as pretty as it is, one is inclined to leave things be but, as a practical matter it should be rephrased to be tail-recursive.

```
let rec transpose (ls : 'a list list) : 'a list list =
let rec transpose_rec acc = function
| [] | [] :: _ -> List.rev acc
| ls -> transpose_rec (List.map (List.hd) ls :: acc) (List.map (List.tl) ls)
in transpose_rec [] ls
```

References:

"An Introduction to Functional Programming Systems Using Haskell" -- Davie A J T., 1992