在Haskell中从矩阵中提取对角线的最佳方法是什么？ [英] What is the best way to extract a diagonal from a matrix in 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）还是像上面显示的头函数？

<编辑：其实更多的是好奇的探究，而不是功课，他们没有在这里教技术大学的函数式编程（这是我认为的一个可怜），但是我会留下标签。

<您可以将原来的定义简化为：

  mainDiagonal：
解决方案
 ：[[a]]  - > [a] 
 mainDiagonal [] = [] 
 mainDiagonal（x：xs）= head x：getDiagonal（map tail xs）
  

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

  mainDiagonal xs = zipWith（!!）xs [0 ..] 
  

Array -based representation

您也可以使用 Data.Array 由（i，j）索引。这可以让你几乎逐字地使用主对角线的数学定义：

$ p $ import $ Data $ Array

mainDiagonal ::（Ix i）=> Array（i，i）e - > [e]
mainDiagonal xs = [e | （（i，j），e）< - assocs xs，i == j]

你可以像这样使用：

   -  n×n矩阵帮助
矩阵n = listArray（（0,0） ，（n-1，n-1））
 
> mainDiagonal $ matrix 3 [1 ..] 
 [1,5,9] 
  

效率

mainDiagonal 的前一个定义仍然没有效率：它仍然需要O $ c> i == j 。类似于 zipWith 版本，它可以被固定和概括如下：

  mainDiagonal xs =（xs！）`map` zip [n..n'] [m..m'] 
其中（（n，m），（n'，m'））= bounds xs 
  

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

I was asked to write a function that would extract the diagonal of a matrix stored as a list of lists. The first version was to extract the number by indexing the lists, but I soon concluded it isn't a good algorithm for Haskell and wrote another function:

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

Since I've only started learning Haskell I'm not sure if it's written in an idiomatic way or if it would perform well.

So my question is is there any better way to extract a diagonal from matrix stored in such a representation or if there isn't is there a better algorithm that could be constructed if the matrix was represented using higher order Haskell concepts, like algebraic types? Also is there any performance difference between deconstructing the list in pattern matching like so ((x:_):xs) or with the head function like shown above?

EDIT: Actually more of curious inquiry than a homework, they don't teach functional programming at technical universities here (which is a pitty I think), but I'll leave the tag.

解决方案

You can simplify your original definition to:

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

There isn't much wrong with using indexing for this, which lets you simplify it further to:

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

Array-based representation

You can also represent matrixes using Data.Array indexed by (i,j). This lets you use the mathematical definition of the main diagonal almost verbatim:

import Data.Array

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

You can use this like:

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

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

Efficiency

The previous definition of mainDiagonal is still not efficient: it still needs O(N²) tests of i == j. Analogous to the zipWith version, it can be fixed and generalized as follows:

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

This version only indexes the array O(N) times. (As a bonus, it also works with rectangular matrices, and is independent of the indexing base.)

这篇关于在Haskell中从矩阵中提取对角线的最佳方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！