algorithm - 帮助算法来计算(四叉树)矩阵的列总和？

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

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)，则输出A重复2 ^ (n - 1)乘以值c * 2 ^ (n - 1)。示例：第一个四叉树是(C 5)所以我们重复5 * 2^(2 - 1) = 10，2 ^ (n - 1) = 2次，得到[5，5]。
否则，给定a和c（以及b和d）的colsum。
当然，这不起作用（甚至不编译），因为经过一些递归之后，我们有：

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

任何想法都会很好，非常感谢。。。

最佳答案

让我们考虑一下您的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 a b c d) = ...的行。
让我们想想类型。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的部分和列表，然后函数应该开始工作。

关于algorithm - 帮助算法来计算(四叉树)矩阵的列总和？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4929295/