列表列表的转置

Question

我正在尝试创建一个递归函数来获取列表列表的转置，从 nx p 到 px n。但我无法这样做。我已经能够创建一个函数，将 3 x n 列表转置为 nx 3 列表：

let rec drop1 list=
    [(match (List.nth list 0) with [] -> [] | a::b -> b);
     (match (List.nth list 1) with [] -> [] | a::b -> b);
     (match (List.nth list 2) with [] -> [] | a::b -> b);]

let rec transpose list=
    if List.length (List.nth list 0) == 0 then []
    else [(match (List.nth list 0) with [] -> 0 | a::b -> a);
          (match (List.nth list 1) with [] -> 0 | a::b -> a);
          (match (List.nth list 2) with [] -> 0 | a::b -> a)]
         :: transpose (drop1 list)

但我无法概括它。我肯定是在思考错误的方向。这可以概括吗？有更好的解决方案吗？请帮忙。

Answer 1

let rec transpose list = match list with
| []             -> []
| []   :: xss    -> transpose xss
| (x::xs) :: xss ->
    (x :: List.map List.hd xss) :: transpose (xs :: List.map List.tl xss)

利用自首次发布答案以来的语法更改：

let rec transpose list = match list with
| []             -> []
| []      :: xss -> transpose xss
| (x::xs) :: xss ->
    List.(
      (x :: map hd xss) :: transpose (xs :: map tl xss)
    )

Answer 2

我知道这是一个老问题，但我最近必须解决这个问题，作为我正在进行的练习的一部分，我遇到了 @sepp2k 的解决方案，但我无法理解它是如何工作的，所以我尝试通过我。

这本质上是相同的算法，但更简洁一些，因为它不会破坏列表的列表。我想我会将其发布在这里，以防其他人正在搜索，并且可能会发现这种表达方式很有用：

let rec transpose = function
   | [] 
   | [] :: _ -> []
   | rows    -> 
       List.map List.hd rows :: transpose (List.map List.tl rows)

Answer 3

假设矩阵是矩形的（否则将引发 Invalid_argument "map2"）：

let transpose m =
  if m = [] then [] else
  List.(fold_right (map2 cons) m @@ map (fun _ -> []) (hd m))

请注意，map (fun _ -> []) (hd m) 只是创建一个列表空列表，长度等于 m 中的列数。

所以这段代码的更清晰的表示是：

let transpose m =
  if m = [] then [] else
  let open List in
  let empty_rows = map (fun _ -> []) (hd m) in
  fold_right (map2 cons) m empty_rows