How do I go about creating a function which will transpose a list without using recursion?

This is what I've gotten so far:

let lst = [[1;2;3];[4;5;6];[7;8;9]]
let transpLstLst (lst: 'a list list) -> 'a list list =
    List.map List.head lst :: []

Which returns:

[[1;4;7]]

This is a long the lines of the output I want, but how do I go from that to being able to get to this output:

[[1;4;7];[2;5;8];[3;6;9]]

CodePudding user response：

This is very inefficient*, but it meets your requirements:

let transpose (matrix : List<List<_>>) =
    [
        if matrix.Length > 0 then
            assert(matrix |> List.distinctBy List.length |> List.length = 1)
            for i = 0 to matrix.[0].Length - 1 do
                yield [
                    for list in matrix do
                        yield list.[i]
                ]
    ]

Example:

let matrix = [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]; [10; 11; 12]]
transpose matrix |> printfn "%A"   // [[1; 4; 7; 10]; [2; 5; 8; 11]; [3; 6; 9; 12]]

* O(n³) where n is the length of a square matrix.

CodePudding user response：

For better performance, you can convert the list of list to an Array2D, and then create your transposed list from the Array2D.

let transpose' xss =
    let xss  = array2D xss
    let dimx = Array2D.length1 xss - 1
    let dimy = Array2D.length2 xss - 1
    [   for y=0 to dimy do [
            for x=0 to dimx do 
                yield xss.[x,y]
        ]
    ]

For non-learning purpose, you should use the built-int List.transpose

 List.transpose lst