在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非常不同，因此那个问题的答案对我不相关。

• 只有一个 这个问题和答案都是关于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] 找到

这类似于将二进制数从0到3计数，即矩阵大小减一。但这种方法太过模糊，无法转换成代码。

- Caridorc

---

Haskell 的更自然的思考方式是：已知第一行和由其余行组成的矩阵上 diagonals 的结果，我们如何构造整个原始矩阵上 diagonals 的结果？ - Reid Barton

数学在IT中的应用 http://math.stackexchange.com/a/22396/5889 - xiamx

Answer 1

从 universe-base-1.0.2.1 开始，您可以直接调用 diagonals 函数。请注意保留 HTML 标签。

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]。）

- Daniel Wagner

---

在某些情况下，使用tail是必要的吗？ - dfeuer

@dfeuer 不是必要的；但总是从一个空列表开始似乎并不是特别有用。 - Daniel Wagner

有没有其他方法可以跳过它？ - dfeuer

@dfeuer 很有可能！你有什么想法？ - Daniel Wagner

我不喜欢使用部分函数来实现完全函数，除非懒惰需要。在这种情况下，我猜你可以特别处理第一步以避免它，但我还没有尝试过。 - dfeuer

@dfeuer 您可以通过“展开”循环一步来避免使用 tail。在这种情况下，我认为总体论证足够局部化（我们在 go 上调用 tail，它始终以 (:) 开头），因此避免在此处重复代码是合理的。另一种选择是在 tail 的位置使用 drop 1；也许如果我在编写此代码时想到了这一点，我会这样做，但我不确定它是否值得现在更改。 - Daniel Wagner

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来修复这个问题。

- Tobias Weck

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 .。

- thomie

---

我其实不在乎顺序排序。 - Caridorc

rotate180 似乎有点奇怪。用 map reverse . reverse 不就可以了吗？ - dfeuer

Answer 4

另一个解决方案:

diagonals = map concat
          . transpose
          . zipWith (\ns xs -> ns ++ map (:[]) xs)
                    (iterate ([]:) [])

基本上，我们将

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

转化为

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

然后对列表进行转置和连接。对角线按相反顺序排列。

但这并不是非常高效，并且无法用于无限列表。

- effectfully

Answer 5

以下是一种方法：

f :: [[a]] -> [[a]]
f vals = 
    let n = length vals
    in [[(vals !! y) !! x | x <- [0..(n - 1)], 
                            y <- [0..(n - 1)], 
                            x + y == k] 
        | k <- [0 .. 2*(n-1)]]

例如，在GHCi中使用它：

Prelude> let f vals = [ [(vals !! y) !! x | x <- [0..(length vals) - 1], y <- [0..(length vals) - 1], x + y == k] | k <- [0 .. 2*((length vals) - 1)]]

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

假设有一个n x n的正方形矩阵，它将有n + n - 1个对角线（这是k迭代的内容），而对于每个对角线，不变量是行和列索引之和等于对角线值（从左上角的零索引开始）。您可以交换项目访问顺序（将!! y !! x与!! x !! y交换），以反转对矩阵进行光栅扫描的顺序。

- ely

---

谢谢，我对这个回复的速度和清晰度印象深刻。但请将 f 重命名为 diagonals，因为 Haskell 已经有足够多的单字母名称了 ;P - Caridorc

抱歉，但我必须说我不喜欢这个解决方案。首先，在列表中应该尽量避免使用过多的"!!" （与向量不同）。其次，它循环遍历"y<-[0..n-1]"只是为了找到"x+y==k"的解决方案，而这有一个非常简单的闭合形式。第三，应该说明解决方案的复杂度。虽然人们希望是O(n^2)的解决方案，但上述内容在我看来看起来像是O(n^5)。 - chi