Помогите с алгоритмом вычисления суммы столбцов матрицы (quadtree)?

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]. Основная идея состоит в суммировании каждого субдерева:

• Если quadtree равен (C c), выведите повторяющееся 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).

Конечно, не работает (даже не компилируется), потому что после некоторой рекурсии мы имеем:

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

Вероятно, "кто-то" должен был объяснить тем, кого беспокоит глубина QuadTree, что поле nexp в типе Matrix предназначено именно для того, чтобы использовать его для определения реального размера (C _).

О решении, представленном в первом ответе, хорошо, оно работает. Однако, совершенно бесполезно строить и деконструировать мат, этого можно легко избежать. Более того, вызов fromIntegral для «обхода» проблемы проверки типа, возникающей из-за использования репликации, может быть решен без необходимости сначала переходить к Integral, а затем возвращаться, как

пусть m = 2 ^ n; k = 2 ^ n в дубликате k (m * x)

В любом случае, задача здесь состоит в том, чтобы избежать квадратичного поведения из-за ++, что я и ожидал.

Приветствия

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 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, тогда ваша функция должна начать работать.

Answer 3

Давайте пойдем более общим образом и вернемся к поставленной цели.

Рассмотрим, как мы должны проецировать квадродерево в матрицу 2 ⁿ × 2 ⁿ ,Возможно, нам не нужно создавать эту проекцию для расчета сумм столбцов, но с ней полезно работать.

• Если наше дерево квадрантов - это одна ячейка, тогда мы просто заполним всюматрица со значением этой ячейки.
• В противном случае, если n ≥ 1, мы можем разделить матрицу на квадранты и позволить каждому субквадратию заполнить каждый квадрант (то есть, чтобы каждое субквадрие заполняло 2 ^n-1 × 2 ^n-1 (матрица).
• Обратите внимание, что все еще остается дело.Что если n = 0 (то есть у нас матрица 1 × 1) и квадродерево не является отдельной ячейкой?Нам нужно указать какое-то поведение для этого случая - возможно, мы просто позволим одному из подквадродеревьев заполнить всю матрицу или заполним матрицу некоторым значением по умолчанию.

Теперь рассмотрим суммы столбцов такогопроекция.

• Если наше квадродерево было одной ячейкой, то суммы столбцов в 2 ⁿ будут в 2 ⁿ раз больше значения, хранящегося в этой ячейке.

  (подсказка: посмотрите на replicate и genericReplicate в hoogle).

• В противном случае, если n ≥ 1, каждый столбец перекрывается двумя разными квадрантами.Половина наших столбцов будет полностью определена западными квадрантами, а другая половина - восточными квадрантами. Сумма для определенного столбца может быть определена как сумма вклада в этот столбец из его северной половины (то есть столбцасумма для этого столбца в северном квадранте) и его южной половины (аналогично).

  (подсказка: нам нужно будет добавить суммы западного столбца к суммам восточного столбца, чтобы получить все суммы столбцов, иобъедините северную и южную суммы полуколонок, чтобы получить действительные суммы для каждого столбца).

• Опять же, у нас есть третий случай, и сумма столбца здесь зависит от того, как вы спроектируете четыресубдеревья на матрицу 1 × 1.К счастью, матрица 1 × 1 означает только сумму в один столбец!

Теперь нам важен только конкретный прогноз - проекция на матрицу размером 2 ^{d * 1048.* d × 2 d где d - глубина нашего дерева квадрантов.Таким образом, вам нужно будет определить глубину тоже.Поскольку отдельная ячейка «естественно» вписывается в матрицу размера 1 × 1, это означает, что она имеет глубину 0. Квадрань должна иметь достаточно большую глубину, чтобы каждый ее подкадр мог вписаться в свой квадрант матрицы.}