不递归转置

Question

我该如何创建一个不使用递归来转置列表的函数？

这是我目前得到的：

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 :: []

哪个returns:

[[1;4;7]]

这是我想要的很长的输出行，但是我如何从那里开始才能得到这个输出：

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

Answer 1

这个效率很低*，但是符合你的要求：

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]
                ]
    ]

示例：

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³) 其中 n 是方阵的长度。

Answer 2

为了获得更好的性能，您可以将列表的列表转换为 Array2D，然后从 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]
        ]
    ]

对于非学习目的，您应该使用内置的 List.transpose

 List.transpose lst

不递归转置

Transposing without recursion

f#

transpose

function

list