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

Answer 2

您可以将原始定义简化为：

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

使用索引并没有太大的错误，这可以让您进一步简化为：

mainDiagonal xs = zipWith (!!) xs [0..]

基于数组的表示

您还可以使用 Data.Array 由 (i,j) 索引。这使您几乎可以逐字使用主对角线的数学定义：

import Data.Array

mainDiagonal :: (Ix i) => Array (i, i) e -> [e]
mainDiagonal xs = [ e | ((i,j),e) <- assocs xs, i == j ]

您可以这样使用：

-- n×n matrix helper
matrix n = listArray ((0,0),(n-1,n-1))

> mainDiagonal $ matrix 3 [1..]
[1,5,9]

效率

之前的 mainDiagonal 定义仍然效率不高：它仍然需要 O(N²) 次测试 我==j。类似于 zipWith 版本，它可以被修复并概括如下：

mainDiagonal xs = (xs !) `map` zip [n..n'] [m..m']
                      where ((n,m),(n',m')) = bounds xs

该版本仅索引数组 O(N) 次。 （作为奖励，它也适用于矩形矩阵，并且独立于索引基数。）

Answer 3

sdcwc 已经回答了原来的问题。我想指出的是，将矩阵表示为列表的列表通常效率很低。当长度未知时，列表是很好的选择，矩阵通常具有固定大小。您可以考虑使用平面关联列表或映射来构建矩阵，以及当您实际使用此矩阵运行计算时具有恒定元素访问时间的任何内容。 Data.Array 是一个不错的选择（参见 Piet 的回答）。

如果您在 Haskell 中运行数值计算，则可以使用 hmatrix 包。它有自己的矩阵数据类型， Data.Packed.Matrix，它有一个takeDiag函数来提取对角线。

Data.Packed.Matrix 示例

例如，如果 m 是您的矩阵

ghci> let m = (3><3) [1..]
ghci> :t m
m :: Matrix Double
ghci> m
(3><3)
 [ 1.0, 2.0, 3.0
 , 4.0, 5.0, 6.0
 , 7.0, 8.0, 9.0 ]

，那么您可以像这样提取其对角线：

ghci> takeDiag m
3 |> [1.0,5.0,9.0]

Answer 4

如果性能不那么相关并且您选择这种方法，只需补充一点 Delport 的答案：

diagonal :: [[a]] -> [a]
diagonal [] = []
diagonal (mHead:mTail) = head mHead:diagonal (map tail mTail)

应该注意的是，由于 head 和 <，该函数只能与您知道是方阵的矩阵一起使用代码>尾用法。

对于 n X m 矩阵，您可以实现忽略额外值的函数，使 [[1,2,3], [4,5,6]] 返回 < code>[1,5]：

diagonal [] = []
diagonal ([]:_) = []
diagonal ((rHead:_):mTail) = rHead:diagonal (map tail mTail)

或者实现一个当你的矩阵不是正方形时会抛出错误的版本：

diagonal [] = []
diagonal ([]:_) = error "not a square matrix"
diagonal [x:y:z] = error "not a square matrix"
diagonal ((rHead:_):mTail) = rHead:diagonal (map tail mTail)

对于这两个答案，应该注意的是，如果你的“列表”，它们仍然可能会抛出“意外”错误由于 map tail mTail 调用，lists' 不是矩阵/不统一 ([[1,2], [1]])。