在Haskell中获取矩阵的所有对角线 [英] Getting all the diagonals of a matrix in Haskell

问题描述

二维列表如下所示：

  1 | 2 | 3 
  -   -   -   -   -  
 4 | 5 | 6 
  -   -   -   -   -  
 7 | 8 | 9 
  

或者在纯哈斯克尔中

  [[1,2,3]，[4,5,6]，[7,8,9]] 
  

对角线的预期输出[[1,2,3]，[4,5,6]，[7,8,9]] 是

$ p $ [[1]，[4,2]，[7,5,3]，[ 8，6]，[9]]


编写 allDiagonals （包括反对角线）是微不足道的：



  allDiagonals :: [[a]]  - > [[a]] 
 allDiagonals xss =（对角线xss）++（对角线（rotate90 xss））
  





我对这个问题的研究

StackOverflow中的类似问题

• Python 这个问题与Python中的相同问题有关，但Python和Haskell非常不同，所以这个问题的答案与我无关。




• 只有一个这个问题和答案在Haskell中，但只是关于中心对角线。

Hoogle

搜索 [[a]] - > [b] [/ b]



独立思考

我认为索引是基于x的一种计数，其中x是矩阵中的维数，请看：

  1 | 2 
  -   -   -  
 3 | 4 
  

对角线是 [[1]，[3，2]， [4]]

可以找到

• 1 at matrix [0] [0]


• 3 matrix [1] [0]


• 2 code> matrix [0] [1]


• 1 可以在 matrix [1] [1]

到3，即矩阵大小减1。但这太模糊了，无法翻译成代码。

haskell.org/package/universe-base-1.0.2.1rel =noreferrer> universe-base-1.0.2.1 ，你可以直接调用 diagonals 功能：

  Data.Universe.Helpers>对角线[[1,2,3]，[4,5,6]，[7,8,9]] 
 [[1]，[4,2]，[7,5,3]，[ 8,6]，[9]] 
  

完整的实现如下所示：

  diagonals :: [[a]]  - > [[a]] 
对角线=尾巴。 go [] where 
  - 在检查es_ 
之前，我们开始产生答案的一些应用程序非常关键
 go b es_ = [h | h：_<  -  b]：案例es_ of 
 []  - >转置ts 
 e：es  - >去（e：ts）es 
其中ts = [t | _：t < -  b] 
  

关键想法是我们保留两个列表：一个矩形块我们还没有开始检查，我们有一个五边形块（左上三角形的一个矩形切出！）。对于五边形块，从每个列表中挑选出第一个元素给我们另一个对角线。然后，我们可以添加一个新的行，从矩形的未检查块到我们删除该对角线后留下的内容。

实现可能看起来有点不自然，但它的目的是相当有效和懒惰：我们唯一要做的事情就是将它们分解成头部和尾部，所以这应该是矩阵中元素总数的O（n）;并且我们在完成解构之后立即生成元素，所以它对垃圾收集非常懒惰/友好。它也适用于无限大的矩阵。

（我推出这个版本只是为了你：以前最接近的东西是使用对角线，这只会给你 [1,4,2,7,5,3,8,6,9] 没有你想要的额外结构。）

The two-dimensional list looks like:

1 | 2 | 3
- - - - -
4 | 5 | 6
- - - - -
7 | 8 | 9

Or in pure haskell

[ [1,2,3], [4,5,6], [7,8,9] ]

The expected output for diagonals [ [1,2,3], [4,5,6], [7,8,9] ] is

[ [1], [4, 2], [7, 5, 3], [8, 6], [9] ]

Writing allDiagonals (to include anti-diagonals) is then trivial:

allDiagonals :: [[a]] -> [[a]]
allDiagonals xss = (diagonals xss) ++ (diagonals (rotate90 xss))

My research on this problem

Similar question here at StackOverflow

• Python this question is about the same problem in Python, but Python and Haskell are very different, so the answers to that question are not relevant to me.

• Only one This question and answer are in Haskell, but are only about the central diagonal.

Hoogle

Searching for [[a]] -> [[a]] gave me no interesting result.

Independent thinking

I think the the indexing follows a kind of count in base x where x is the number of dimensions in the matrix, look at:

1 | 2
- - -
3 | 4

The diagonals are [ [1], [3, 2], [4] ]

• 1 can be found at matrix[0][0]
• 3 can be found at matrix[1][0]
• 2 can be found at matrix[0][1]
• 1 can be found at matrix[1][1]

That is similar to counting in base 2 up to 3, that is the matrix size minus one. But this is far too vague to be translated into code.

解决方案

Starting with universe-base-1.0.2.1, you may simply call the diagonals function:

Data.Universe.Helpers> diagonals [ [1,2,3], [4,5,6], [7,8,9] ]
[[1],[4,2],[7,5,3],[8,6],[9]]

The implementation in full looks like this:

diagonals :: [[a]] -> [[a]]
diagonals = tail . go [] where
    -- it is critical for some applications that we start producing answers
    -- before inspecting es_
    go b es_ = [h | h:_ <- b] : case es_ of
        []   -> transpose ts
        e:es -> go (e:ts) es
        where ts = [t | _:t <- b]

The key idea is that we keep two lists: a rectangular chunk we haven't started inspecting, and a pentagonal chunk (a rectangle with the top left triangle cut out!) that we have. For the pentagonal chunk, picking out the first element from each list gives us another diagonal. Then we can add a fresh row from the rectangular, un-inspected chunk to what's left after we delete that diagonal.

The implementation may look a bit unnatural, but it's intended to be quite efficient and lazy: the only thing we do to lists is destructure them into a head and tail, so this should be O(n) in the total number of elements in the matrix; and we produce elements as soon as we finish the destructuring, so it's quite lazy/friendly to garbage collection. It also works well with infinitely large matrices.

(I pushed this release just for you: the previous closest thing you could get was using diagonal, which would only give you [1,4,2,7,5,3,8,6,9] without the extra structure you want.)

这篇关于在Haskell中获取矩阵的所有对角线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！