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

给出上述定义，编写一个谓词来检查给定图像（编码为四叉树）是否关于垂直轴对称（水平对称）。尽可能使用匿名函数。

问题：您将如何对给定的四叉树实施水平对称检查？

好吧，我在想这样的事情：当四叉树只是一片叶子时，在这种情况下我们有水平对称性。基本情况是当四叉树只有一层（四片叶子）对称性时，只需检查颜色即可(c1 == c2 && c3 == c4)。

在任何其他情况下，我可能会检查此条件是否满足递归： nw equals (fliphorizontal(ne)) && sw equals (fliphorizontal(se))，其中fliphorizontal水平翻转四叉树并equals检查两个四叉树是否相等。但是，我想尽可能避免使用外部函数，如果可能的话只使用匿名函数。

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 :: (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)

编辑：最终的单功能解决方案（使用四叉树的广义折叠函数）：

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 :: (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 回答
1

怎么样

ishsymmetric qt = qt == fliph qt
于 2011-02-05T18:53:07.720 回答