这个转置功能如何工作？

Question

我有这个功能由我的教授给出,我不知道实际发生了什么.

这是计算m-by-n矩阵的转置的函数:

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)

测试功能:

> transpose [[1;2;3];[4;5;6]];;
  val it : int list list = [[1; 4]; [2; 5]; [3; 6]]

我理解List.map,递归和所有这些东西.我只是不明白为什么/这个功能如何工作.任何澄清将非常感谢!谢谢!

Answer 1

假设我们有一个3x3矩阵A.

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

= [ R1
    R2
    R3 ]

现在,让我们分析转置函数.

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)

前两个案例抓住了以下事件:

• 该列表是一个空列表
• 该列表包含一个空列表,表示已处理所有内部列表

代码[1]

List.map List.head xs

将内部列表映射到它们各自的头部元素

R1.Head ; R2.Head ; R3.Head
= 1 ; 4 ; 7
= C1

代码[2]

transpose (List.map List.tail xs)

(recursivly)转置斩首列表的尾部.因此,在每次递归时,列都会转换为一行.使用::关键字这些行,然后用于构建结果列表.

transpose A
= C1 :: C2 :: C3 :: []
= [ C1
    C2
    C3 ]
= [ [1;4;7]
    [2;5;8]
    [3;6;9] ]