1

次のように定義された四分木を想像してください。

data (Eq a, Show a) => QT a = C a | Q (QT a) (QT a) (QT a) (QT a)
  deriving (Eq, Show)

bad1 = Q u u u u where u = C 255
bad2 = Q (C 0) (C 255) (Q u u u u) (C 64) where u = C 255

コンストラクターを使用すると、整形式ではない四分木を作成できます。bad1単純に C 255 である必要があり、bad2右下の四分木であるため有効ではありません (同じ理由で、Q (C 0) (C 255) (C 244) (C 64).

ここまでは順調ですね。その整形式をチェックすることは、単純に内部の四分木を再帰的にチェックすることです。基本的なケースは、すべての内側の四分木がリーフである場合です。これにより、すべての色がすべて等しくなるわけではありません。

wellformed :: (Eq a, Show a) => QT a -> Bool
wellformed (Q (C c1) (C c2) (C c3) (C c4)) = any (/= c1) [c2, c3, c4]
wellformed (Q (C c1) (C c2) se (C c4))     = valid se
-- continue defining patters to match e.g Q C C C, C Q Q C, and so on...

質問:葉と四分木の考えられるすべての組み合わせに対して、すべての一致を入力することを避けることはできますか?

私の質問が非常に奇妙である場合は、しばらくお待ちください。

4

1 に答える 1

4

どうでも...

wellformed :: (Eq a, Show a) => QT a -> Bool
wellformed (C _) = True
wellformed (Q (C c1) (C c2) (C c3) (C c4)) = any (/= c1) [c2, c3, c4]
wellformed (Q nw ne se sw) = wellformed nw && wellformed ne
   && wellformed se && wellformed sw

編集:またはさらに良い:

wellformed :: (Eq a, Show a) => QT a -> Bool
wellformed (C _) = True
wellformed (Q (C c1) (C c2) (C c3) (C c4)) = any (/= c1) [c2, c3, c4]
wellformed (Q nw ne se sw) = all wellformed [nw, ne, se, sw]

編集：バインディングが間違っていることに注意してください。次のようにする必要があります：NW NE SW SE!!!

于 2011-02-04T05:20:45.173 に答える