转置矩阵ocaml时冗余[]

Question

我正在测试在OCaml中转换矩阵(type matrix = float list list(的函数，下面是我的代码：

(* get the first column of the matrix *)
let rec get_column (a: matrix): float list = 
match a with
| [] -> []
| x :: xs ->
(match x with
| [] -> []
| h :: t -> h :: get_column xs)
(* get the rest of the element in the matrix *)
let rec get_tail (a: matrix): matrix =
match a with
| [] -> []
| x :: xs ->
(match x with
| [] -> []
| h :: t -> t :: get_tail xs)
(* find the transpose of a matrix *)
let rec transpose (lss : matrix) : matrix =
match lss with
| [] -> []
| _ -> get_column lss :: transpose (get_tail lss)

当我测试它时，在最后有一个多余的[]，我不知道为什么。例如，的输出

transpose[[0.; 4.; 8.]; [1.; 5.; 9.]; [2.; 6.; 10.]; [3.; 7.; 11.]]

应该是

[[0.; 1.; 2.; 3.]; [4.; 5.; 6.; 7.]; [8.; 9.; 10.; 11.]]

但我的代码输出是：

[[0.; 1.; 2.; 3.]; [4.; 5.; 6.; 7.]; [8.; 9.; 10.; 11.]; []]

Answer 1

首先，您可以显著简化模式匹配。

let rec get_column (a: matrix): float list = 
match a with
| [] | []::_ -> []
| (h::_)::xs -> h :: get_column xs
let rec get_tail (a: matrix): matrix =
match a with
| [] | []::_ -> []
| (_::t)::xs -> t :: get_tail xs

完成了这些之后，让我们看看如何评估一个简单的转置调用。

transpose [[1.; 2.]; [3.; 4.]]
[1.; 3.] :: transpose [[2.]; [4.]]
[1.; 3.] :: [2.; 4.] :: transpose [[]; []]
[1.; 3.] :: [2.; 4.] :: [] :: transpose []
[1.; 3.] :: [2.; 4.] :: [] :: []
[[1.; 3.]; [2.; 4.]; []]

从本质上讲，你所做的就是在每个列表中占据首位。这可以通过List.map来完成(如果必须的话，可以实现自己的版本(。

let get_column lss =
List.(map hd lss)

你的get_tail功能基本上只是：

let get_tail lss =
List.(map tl lss)

对于第一行中的每个元素，都需要检索每一列。

let rec transpose lss =
match lss with
| []::_ | [] -> []
| (h::t)::xs -> 
let heads = h :: List.(map hd xs) in
let tails = t :: List.(map tl xs) in
heads :: transpose tails

Answer 2

对于这类错误，您应该测试显示该问题的最简单的案例。在您的情况下，这将是transpose [[0.]]。由于这个例子很小，所以您可以手动跟踪transpose函数的执行情况并发现问题。