3

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

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

我正在尝试编写一个函数,该函数将输出列 sum的列表,例如:[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]。
  • 否则,给定(Q a b c d),我们zipWith是 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

任何想法都会很棒,非常感谢......

4

3 回答 3

2

可能“某人”应该向担心四叉树深度的人解释,Matrix 类型中的 nexp 字段恰好用于确定 (C_) 的实际大小。

关于第一个答案中提出的解决方案,好的。然而,构造和解构 Mat 是毫无用处的,这可以很容易地避免。此外,调用 fromIntegral 以“绕过”来自使用复制的类型检查问题可以在不强制先进入 Integral 然后再返回的情况下解决,例如

让 m = 2^n; k=2^n 在复制 k (m*x)

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

干杯,

于 2011-02-09T11:08:26.857 回答
1

让我们考虑一下您的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您的函数应该开始工作。

于 2011-02-08T13:53:01.197 回答
0

让我们更笼统地说,回到手头的目标。

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

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

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

  • 如果我们的四叉树是单个单元格,那么 2 n列的总和将全部是 存储在该单元格中的值的2 n倍。

    (提示:查看replicategenericReplicate上 hoogle)。

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

    (提示:我们需要将西列总和附加到东列总和以获得所有列总和,并结合北部和南部半列总和以获得每列的实际总和)。

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

现在,我们只关心一个特定的投影——投影到大小为 2 d d×2 d的矩阵上, 其中 d 是四叉树的深度。所以你也需要计算深度。由于单个单元格“自然地”适合大小为 1×1 的矩阵,这意味着它的深度为 0。四边形必须具有足够大的深度,以允许其每个子四边形适合矩阵的象限。

于 2011-02-09T01:45:12.443 回答