How does this transpose function work?
I have this function given by my professor and I have no idea what is actually going on.
Here is a function that calculates the transposition 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)
Function testing:
> 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. I just don't understand why / how this feature works. Any clarification would be much appreciated! Thank you!
source to share
Let's say we have a 3x3 matrix A
.
let A =
[ [1;2;3]
[4;5;6]
[7;8;9] ]
= [ R1 R2 R3 ]
Now let's analyze 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 capture events where:
- list is an empty list
- the list contains an empty list, that is, all internal lists have been processed
Code [1]
List.map List.head xs
maps inner lists to corresponding head elements
R1.Head ; R2.Head ; R3.Head = 1 ; 4 ; 7 = C1
Code [2]
transpose (List.map List.tail xs)
(recursively) wraps the tails of decapitated lists. This way, on each recursion, the column wraps to the row. Using the keyword ::
, these strings are then used to build the resulting list.
transpose A = C1 :: C2 :: C3 :: [] = [ C1 C2 C3 ] = [ [1;4;7] [2;5;8] [3;6;9] ]
source to share