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

Question

二维列表如下所示:

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

或者在纯 haskell

[ [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 非常不同，所以这个问题的答案与我无关。

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

胡歌
搜索 [[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，即矩阵大小减一。但这太模糊了，无法翻译成代码。

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]

关键的想法是我们保留两个列表:一个我们还没有开始检查的矩形 block ，以及一个我们已经拥有的五边形 block (一个左上角三角形被剪掉的矩形!)。对于五边形 block ，从每个列表中挑选出第一个元素会给我们另一个对角线。然后我们可以从矩形的、未经检查的 block 中添加一个新行到我们删除该对角线后剩下的部分。

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

(我为您推送了这个版本:之前您能得到的最接近的东西是使用 diagonal ，它只会给您 [1,4,2,7,5,3,8,6,9] 没有您想要的额外结构。)