帮助计算（四叉树）矩阵的列和的算法？

Question

给定这个定义和一个测试矩阵：

data (Eq a, Show a) => QT a = C a | Q (QT a) (QT a) (QT a) (QT a)
    deriving (Eq, Show)

data (Eq a, Num a, Show a) => Mat a = Mat {nexp :: Int, mat :: QT a}
    deriving (Eq, Show)

-- test matrix, exponent is 2, that is matrix is 4 x 4
test = Mat 2 (Q (C 5) (C 6) (Q (C 1) (C 0) (C 2) (C 1)) (C 3))

|     |     |
|  5  |  6  |
|     |     |
-------------
|1 | 0|     |
|--|--|  3  |
|2 | 1|     |

我正在尝试编写一个函数来输出列总和列表，例如：[13, 11, 18, 18] 。基本思想是对每个子四叉树求和：

• 如果四叉树是 (C c)，则输出重复 2 ^ (n - 1) 乘以值 >c * 2 ^ (n - 1)。 示例：第一个四叉树是 (C 5) 所以我们重复 5 * 2^(2 - 1) = 10, 2 ^ (n - 1) = 2次，得到[5, 5]。
• 否则，给定 (Q abcd)，我们 zipWith a 和 c（以及 b 和 d）的余和。

当然，这是不起作用（甚至无法编译），因为经过一些递归之后，我们得到了：

zipWith (+) [[10, 10], [12, 12]] [zipWith (+) [[1], [0]] [[2], [1]], [6, 6]]

因为我从Haskell开始，我觉得我错过了一些东西，需要一些关于我可以使用的函数的建议。 不起作用 colsum 的定义是：

colsum :: (Eq a, Show a, Num a) => Mat a -> [a]
colsum m = csum (mat m)
    where
        n = nexp m
        csum (C c)       = take (2 ^ n) $ repeat (c * 2 ^ n)
        csum (Q a b c d) = zipWith (+) [colsum $ submat a, colsum $ submat b]
                                       [colsum $ submat c, colsum $ submat d]
        submat q = Mat (n - 1) q

任何想法都会很棒并且非常感激......

Answer 1

也许“某人”应该向担心四叉树深度的人解释，矩阵类型中的 nexp 字段正是用于确定 (C _) 的实际大小。

关于第一个答案中提出的解决方案，好的，它有效。然而构造和解构 Mat 是毫无用处的，这是很容易避免的。此外，调用 fromIntegral 来“绕过”由于使用复制而产生的类型检查问题可以得到解决，而无需强制先进入 Integral 然后再返回，就像

let m = 2^n;复制 k (m*x) 中的 k=2^n

无论如何，这里的挑战是避免由于 ++ 导致的二次行为，这就是我所期望的。

干杯，

Answer 2

让我们考虑一下您的 colsum：

colsum :: (Eq a, Show a, Num a) => Mat a -> [a]
colsum m = csum (mat m)
    where
        n = nexp m
        csum (C c)       = take (2 ^ n) $ repeat (c * 2 ^ n)
        csum (Q a b c d) = zipWith (+) [colsum $ submat a, colsum $ submat b]
                                       [colsum $ submat c, colsum $ submat d]
        submat q = Mat (n - 1) q

它几乎是正确的，除了您定义 csum (Q abcd) = ... 的行。

让我们考虑一下类型。 colsum 返回数字列表。 ZipWith (+) 按元素对两个列表求和：

ghci> :t zipWith (+)
zipWith (+) :: Num a => [a] -> [a] -> [a]

这意味着您需要将两个数字列表传递给 zipWith (+)。相反，您可以创建两个数字列表列表，如下所示：

[colsum $ submat a, colsum $ submat b]

此表达式的类型是 [[a]]，而不是您需要的 [a]。

您需要做的是连接两个数字列表以获得单个数字列表（这可能就是您想要做的）：

((colsum $ submat a) ++ (colsum $ submat b))

类似地，您连接 c 的部分和列表和 d 那么你的函数应该开始工作。

Answer 3

让我们更笼统地讨论一下，然后回到手头的目标。

考虑如何将四叉树投影到 2ⁿ×2ⁿ 矩阵中。我们可能不需要创建此投影来计算其列总和，但这是一个有用的概念。

• 如果我们的四叉树是单个单元格，那么我们只需用该单元格的值填充整个矩阵即可。
• 否则，如果 n ≥ 1，我们可以将矩阵分成象限，并让每个子四叉树填充一个象限（即让每个子四叉树填充一个 2^n-1×2^{n -1矩阵）。}
• 请注意，还有一个案例尚未完成。如果 n = 0（即我们有一个 1×1 矩阵）并且四叉树不是单个单元怎么办？我们需要为这种情况指定一些行为 - 也许我们只是让子四叉树之一填充整个矩阵，或者我们用一些默认值填充矩阵。

现在考虑这种投影的列总和。

• 如果我们的四叉树是单个单元格，则 2ⁿ 列的总和将为 2ⁿ
  乘以该单元格中存储的值。

  （提示：查看 hoogle 上的 replicate 和 genericReplicate）。

• 否则，如果 n ≥ 1，则每列与两个不同的象限重叠。
  我们一半的柱子将完全由西象限决定，
  另一半是东象限，特定列的总和
  可以定义为该列贡献的总和
  从其北半部分（即北象限中该列的列总和），
  及其南半部（同样）。

  （提示：我们需要将西列总和附加到东列总和
  获取所有列的总和，并合并北部和南部的半列总和
  以获得每列的实际总和）。

• 同样，我们有第三种情况，这里的列总和取决于如何
  将四个子四叉树投影到 1×1 矩阵上。幸运的是，1×1 矩阵意味着
  只有一个列总和！

现在，我们只关心一个特定的投影 - 到大小为 2^dd×2^d 的矩阵上的投影
其中 d 是四叉树的深度。所以你还需要计算深度。自从一个
单个细胞“自然地”适合大小为 1×1 的矩阵，这意味着它具有
深度为 0。四分支必须具有足够大的深度以允许其每个子四分支相适应
进入矩阵的象限。