在Haskell中获取矩阵的所有对角线

Question

二维列表如下:

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

或者在纯粹的哈克尔

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

预期的输出diagonals [ [1,2,3], [4,5,6], [7,8,9] ]是

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

写作allDiagonals(包括反对角线)是微不足道的:

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

我对这个问题的研究

类似的问题在StackOverflow

• Python这个问题是关于Python中的同样问题,但Python和Haskell是非常不同的,所以这个问题的答案与我无关.

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

Hoogle

搜索给[[a]] -> [[a]]了我没有有趣的结果.

独立思考

我认为索引遵循基数x中的一种计数,其中x是矩阵中的维数,请看:

1 | 2
- - -
3 | 4

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

• 1 可以找到 matrix[0][0]
• 3 可以找到 matrix[1][0]
• 2 可以找到 matrix[0][1]
• 1 可以找到 matrix[1][1]

这类似于在基数2中计数到3,即矩阵大小减1.但这太过模糊,无法翻译成代码.

Answer 1

从universe-base-1.0.2.1开始,您可以简单地调用该diagonals函数:

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

完整的实现看起来像这样:

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]

关键的想法是我们保留两个列表:一个我们还没有开始检查的矩形块,以及我们拥有的五边形块(一个左上角三角形的矩形!).对于五边形块,从每个列表中挑选出第一个元素会给我们另一个对角线.然后我们可以在删除该对角线后,从未经检查的矩形块中添加一个新行.

实现可能看起来有点不自然,但它的目的是非常有效和懒惰:我们对列表做的唯一事情就是将它们分解为头部和尾部,因此这应该是O(n)中元素的总数.矩阵; 我们在完成解构后立即生成元素,因此垃圾收集非常懒惰/友好.它也适用于无限大的矩阵.

(我推出这个版本只是为了你:你可以得到的最接近的东西是使用diagonal,这只会给你[1,4,2,7,5,3,8,6,9]没有你想要的额外结构.)

Answer 2

这是一个递归版本，假设输入总是格式良好的：

diagonals []       = []
diagonals ([]:xss) = xss
diagonals xss      = zipWith (++) (map ((:[]) . head) xss ++ repeat [])
                                  ([]:(diagonals (map tail xss)))

它以递归方式工作，从一列到另一列。将一列的值与矩阵中减去一列的对角线相结合，移动一行以实际获得对角线。希望这个解释有意义。

举例说明：

diagonals [[1,2,3],[4,5,6],[7,8,9]]
= zipWith (++) [[1],[4],[7],[],[],...] [[],[2],[5,3],[8,6],[9]]
= [[1],[4,2],[7,5,3],[8,6],[9]]

另一个适用于行而不是列的版本，但基于相同的想法：

diagonals []       = repeat []
diagonals (xs:xss) = takeWhile (not . null) $
    zipWith (++) (map (:[]) xs ++ repeat [])
                 ([]:diagonals xss)

与指定的结果相比，生成的对角线反转。这当然可以通过应用来解决map reverse。

Answer 3

import Data.List

rotate90 = reverse . transpose
rotate180 = rotate90 . rotate90

diagonals = (++) <$> transpose . zipWith drop [0..]
                 <*> transpose . zipWith drop [1..] . rotate180

它首先得到主（[1,5,9]）和上对角线（[2,6]和[3]）；然后是下对角线：[8,4]和[7]。

如果您关心排序（即您认为应该说[4,8]而不是[8,4]），请map reverse .在最后一行插入 a 。