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]。基本的な考え方は、各サブ四分木を合計することです。

  • quadtree が(C c)の場合、値 の繰り返し2 ^ (n - 1)回数を出力しますc * 2 ^ (n - 1)。例: 最初の四分木は、[5, 5] を取得(C 5)して を繰り返します。5 * 2^(2 - 1) = 102 ^ (n - 1) = 2
  • そうでなければ、与えられた(Q a b c d)、zipWitha と c (および b と d) の colsum です。

もちろん、これは機能していません(コンパイルすらしていません)。

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

私は Haskell を使い始めているので、何かが足りないと感じています。使用できる機能についてアドバイスが必要です。コルサムの定義が機能しない:

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

おそらく「誰か」は、QuadTree の深さを心配している人に、Matrix 型の nexp フィールドが (C _) の実際のサイズを決定するために使用されることを正確に説明しているはずです。

最初の回答で提示された解決策については、うまくいきます。ただし、Mat を構築および分解することはまったく役に立ちません。これは簡単に回避できます。さらに、レプリケートの使用に起因する型チェックの問題を「バイパス」するための fromIntegral の呼び出しは、次のように、最初に Integral に移動してから戻ることを強制することなく解決できます。

m = 2^n とします。k=2^n の複製 k (m*x)

とにかく、ここでの課題は、++ による 2 次動作を回避することです。これは私が期待することです。

乾杯、

于 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 (+)2 つのリストを要素ごとに合計します。

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

これは、2 つの数値リストを に渡す必要があることを意味しますzipWith (+)。代わりに、次のように、数値のリストの 2 つのリストを作成します。

[colsum $ submat a, colsum $ submat b]

この式の型は で、必要に応じてでは[[a]]ありません。[a]

あなたがする必要があるのは、2 つの数字のリストを連結して、1 つの数字のリストを取得することです (おそらく、これが意図したことです)。

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

同様に、部分和のリストを連結するcとd、関数が機能し始めます。

于 2011-02-08T13:53:01.197 に答える
0

より一般的な話をして、目の前の目標に戻りましょう。

四分木を 2 n ×2 n行列に射影する方法を考えてみましょう。列の合計を計算するためにこのプロジェクションを作成する必要はないかもしれませんが、使用すると便利な概念です。

  • 四分木が単一のセルの場合、マトリックス全体をそのセルの値で埋めます。
  • それ以外の場合、n ≥ 1 の場合、行列を四分円に分割し、サブ四分木でそれぞれ 1 つの四分円を埋めることができます (つまり、各サブ四分木で 2 n-1 ×2 n-1行列を埋めます)。
  • まだケースが残っていることに注意してください。n = 0 (つまり、1 × 1 の行列がある) で、四分木が単一のセルではない場合はどうなるでしょうか? この場合の動作を指定する必要があります。部分四分木の 1 つにマトリックス全体を入力させるか、マトリックスにデフォルト値を入力します。

次に、そのような射影の列の合計を考えてみましょう。

  • 四分木が単一のセルである場合、2 n列の合計はすべて 、そのセルに格納されている値の2 n倍になります。

    (ヒント: hoogle を見てください) replicate。genericReplicate

  • それ以外の場合、n ≥ 1 の場合、各列は 2 つの異なる象限に重なっています。列の半分は西の象限によって完全に決定され、残りの半分は東の象限によって決定されます。特定の列の合計は、その列の北半分 (つまり、列北象限のその列の合計)、およびその南半分 (同様に)。

    (ヒント: 西の列の合計を東の列の合計に追加してすべての列の合計を取得し、北と南の半列の合計を組み合わせて各列の実際の合計を取得する必要があります)。

  • ここでも 3 番目のケースがあり、ここでの列の合計は、4 つの部分四分木を 1×1 行列にどのように射影するかによって異なります。幸いなことに、1×1 行列は 1 列の合計のみを意味します!

ここで、特定の射影、つまりサイズ 2 d d×2 dの行列への射影のみを 考慮します。ここで、d は四分木の深さです。そのため、奥行きも把握する必要があります。単一のセルはサイズ 1×1 のマトリックスに「自然に」適合するため、深さが 0 であることを意味します。クワッドブランチには、そのサブクワッドのそれぞれがマトリックスの象限に適合するのに十分な深さが必要です。

于 2011-02-09T01:45:12.443 に答える