algorithm - 从 Haskell 中的矩阵中提取对角线的最佳方法是什么？

Question

我被要求编写一个函数来提取存储为列表列表的矩阵的对角线。第一个版本是通过索引列表来提取数字，但我很快得出结论，这对 Haskell 来说不是一个好的算法并编写了另一个函数:

getDiagonal :: (Num a) => [[a]] -> [a]
getDiagonal [[]]       = []
getDiagonal (xs:[])    = [head xs]
getDiagonal (x:xs)     = head x : getDiagonal (map tail xs)

由于我才刚刚开始学习 Haskell，所以我不确定它是否以惯用的方式编写，或者它是否会表现良好。

所以我的问题是有没有更好的方法从存储在这种表示中的矩阵中提取对角线，或者如果没有更好的算法可以构造，如果矩阵是使用高阶 Haskell 概念表示的，比如代数类型？另外，在像这样 ((x:_):xs) 这样的模式匹配中解构列表或像上面显示的那样使用 head 函数解构列表之间是否有任何性能差异？

编辑:实际上更多的是好奇的询问而不是家庭作业，他们在这里的技术大学不教授函数式编程(我认为这很可惜)，但我会留下标签。

Answer 1

我认为使用索引是可以的，如果你可以假设参数是一个方阵。无论如何，使用这种表示法获得对角线是 O(N²)，因为您必须遍历列表。

diag x = zipWith (!!) x [0..]