Help with algorithm for compute columns sum of a (quadtree) matrix?

Question

Given this definition and a test matrix:

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

I'm trying to write a function that will output a list of columns sum, like: [13, 11, 18, 18]. The base idea is to sum each sub-quadtree:

• If quadtree is (C c), then output the a repeating 2 ^ (n - 1) times the value c * 2 ^ (n - 1). Example: first quadtree is (C 5) so we repeat 5 * 2^(2 - 1) = 10, 2 ^ (n - 1) = 2 times, obtaining [5, 5].
• Otherwise, given (Q a b c d), we zipWith the colsum of a and c (and b and d).

Of course this is not working (not even compiling) because after some recursion we have:

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

Because I'm beginning with Haskell I feel I'm missing something, need some advice on function I can use. Not working colsum definition is:

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

Any ideas would be great and much appreciated...

Answer 1

Let's consider your 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

It is almost correct, except the line where you define csum (Q a b c d) = ....

Let think about types. colsum returns a list of numbers. ZipWith (+) sums two lists elementwise:

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

This means that you need to pass two lists of numbers to zipWith (+). Instead you create two lists of lists of numbers, like this:

[colsum $ submat a, colsum $ submat b]

The type of this expression is [[a]], not [a] as you need.

What you need to do is to concatenate two lists of numbers to obtain a single list of numbers (and this is, probably, what you intended to do):

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

Similarly, you concatenate lists of partial sums for c and d then your function should start working.

Answer 2

Let's go more general, and come back to the goal at hand.

Consider how we would project a quadtree into a 2ⁿ×2ⁿ matrix. We may not need to create this projection in order to calculate its column sums, but it's a useful notion to work with.

• If our quadtree is a single cell, then we'd just fill the entire matrix with that cell's value.
• Otherwise, if n ≥ 1, we can divide the matrix up into quadrants, and let the subquadtrees each fill one quadrant (that is, have each subquadtree fill a 2^n-1×2^n-1 matrix).
• Note that there's still a case remaining. What if n = 0 (that is, we have a 1×1 matrix) and the quadtree isn't a single cell? We need to specify some behaviour for this case - maybe we just let one of the subquadtrees populate the entire matrix, or we fill the matrix with some default value.

Now consider the column sums of such a projection.

• If our quadtree was a single cell, then the 2ⁿ column sums will all be 2ⁿ times the value stored in that cell.

  (hint: look at replicate and genericReplicate on hoogle).

• Otherwise, if n ≥ 1, then each column overlaps two distinct quadrants. Half of our columns will be completely determined by the western quadrants, and the other half by the eastern quadrants, The sum for a particular column can be defined as the sum of the contribution to that column from its northern half (that is, the column sum for that column in the northern quadrant), and its southern half (likewise).

  (hint: We'll need to append the western column sums to the eastern column sums to get all the column sums, and combien the northern and southern demi-column sums to get the actual sums for each column).

• Again, we have a third case, and the column sum here depends on how you project four subquadtrees onto a 1×1 matrix. Fortunately, a 1×1 matrix means only a single column sum!

Now, we only care about a particular projection - the projection onto a matrix of size 2^dd×2^d where d is the depth of our quadtree. So you'll need to figure the depth too. Since a single cell fits "naturally" into a matrix of size 1×1, that implies that it has a depth of 0. A quadbranch must have depth great enough to allow each of its subquads to fit into their quadrant of the matrix.

Answer 3

Probably "someone" should have explained to who is worried about the depth of the QuadTree that the nexp field in the Matrix type is exactly meant to be used to determine the real size of a (C _).

About the solution presented in the first answer, ok it works. However it is quite useless to construct and deconstruct Mat, this could be easily avoided. Moreover the call to fromIntegral to "bypass" the type checking problem coming from the use of replicate can be solved without forcing to first going to Integral and then coming back, like

let m = 2^n; k=2^n in replicate k (m*x)

Anyway, the challenge here is to avoid the quadratical behavior due to the ++, that is what I would expect.

Cheers,