从Haskell矩阵中提取对角线的最佳方法是什么?
我被要求编写一个函数,该函数将提取存储为列表列表的矩阵的对角线。第一个版本是通过为列表建立索引来提取数字,但我很快得出结论,这对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函数之间,在性能上有什么区别吗?
编辑:实际上,好奇的查询多于作业,他们在这里的技术大学不教函数编程(我认为这很可惜),但我会保留这个标签。
-
您可以将原始定义简化为:
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)次。(此外,它还适用于矩形矩阵,并且独立于索引基数。)
-
计算矩阵中对角线的总和
2021-01-31 关注 0 浏览84 1答案
-
在numpy中更改矩阵的对角线的值
2021-01-29 关注 0 浏览127 1答案
-
检查矩阵中的列或对角线是否= x(无Numpy)
2021-01-29 关注 0 浏览84 1答案
-
从Java中的字符串中提取第一个单词的最佳方法是什么?
2021-01-31 关注 0 浏览144 1答案
-
求一个3*3矩阵对角线元素之和。
2022-05-11 关注 0 浏览19 1答案
-
PandasDataFrame对角线
2021-01-29 关注 0 浏览69 1答案
-
对称矩阵是指元素以主对角线为对称轴对应相等的矩阵,对称矩阵是一个方形矩阵,...
2022-03-02 关注 0 浏览59 1答案
-
如何将下对角线元素的 Numpy 数组转换为完整矩阵的数组
2022-07-28 关注 0 浏览53 1答案
-
如何计算Tensorflow中的所有二阶导数(仅是Hessian矩阵的对角线)?
2021-01-29 关注 0 浏览132 1答案
-
从给定的numpy数组创建块对角线numpy数组
2021-01-29 关注 0 浏览102 1答案