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

上記のように定義を与えて、与えられた画像（四分木としてコード化されている）が垂直軸に関して対称であるかどうかをチェックするための述語を書きます（水平対称）。可能な場合は無名関数を使用してください。

質問：特定の四分木に対して水平対称性チェックをどのように実装しますか？

さて、私はこのようなことを考えていました。四分木が単なる葉である場合、その場合、水平対称になります。基本的なケースは、四分木が1つのレベル（4つのリーフ）しかない場合です。対称性は、色をチェックするだけの問題です(c1 == c2 && c3 == c4)。

それ以外の場合は、この条件が再帰的に満たされているかどうかを確認できます nw equals (fliphorizontal(ne)) && sw equals (fliphorizontal(se))。ここでfliphorizontal、四分木を水平方向に反転し、equals2つの四分木が等しいかどうかを確認します。ただし、外部機能の使用はできるだけ避け、可能であれば匿名の機能のみを使用したいと思います。

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

編集：fliphの例：

fliph :: (Eq a, Show a) => QT a -> QT a
fliph (C a)           = C a
fliph (Q nw ne sw se) = Q (fliph ne) (fliph nw) (fliph se) (fliph sw)

編集：最終的な1関数ソリューション（四分木に一般化されたフォールド関数を使用）：

ishsymmetric :: (Eq a, Show a) => QT a -> Bool
ishsymmetric (C _)       = True
ishsymmetric (Q a b c d) = and $ zipWith equals [a,c] [fliph b,fliph d]
    where
        fold f g (C c)       = g c
        fold f g (Q a b c d) = f (fold f g a) (fold f g b)
                                 (fold f g c) (fold f g d)
        fliph q = fold (\a b c d -> Q b a d c) (\c -> C c) q
        equals (C c1) (C c2)           = c1 == c2
        equals (Q a b c d) (Q e f g h) = and $ zipWith equals [a,b,c,d] [e,f,g,h]
4

2 に答える 2

1

どうですか

ishsymmetric qt = qt == fliph qt
于 2011-02-05T18:53:07.720 に答える
1

何かのようなもの：

ishsymmetric :: (Eq a, Show a) => QT a -> Bool
ishsymmetric (C _)                           = True
ishsymmetric (Q (C c1) (C c2) (C c3) (C c4)) = c1 == c2 && c3 == c4
ishsymmetric (Q nw ne sw se) = equals nw (fliph ne) && equals sw (fliph se)
    where equals (C a) (C b) = a == b
          equals (Q a b c d) (Q e f g h) = equals a e && equals b f && equals c g && equals d h
          fliph (C a)           = C a
          fliph (Q nw ne sw se) = Q (fliph ne) (fliph nw) (fliph se) (fliph sw)

ただし、構文の最適化は可能です。：-/

于 2011-02-05T17:10:54.147 に答える