在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²)测试i == 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 中运行数值计算，则可以使用hmatrixpackage.json 。它有自己的矩阵数据类型 ，Data.Packed.Matrix并且具有takeDiag提取对角线的功能。

数据.打包.矩阵示例

例如，如果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]