检查四叉树水平对称的算法？

Question

检查四叉树水平对称的算法？

algorithmhaskellfunctional-programmingquadtree

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等于(fliphorizontal(ne)) && sw等于(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 示例:

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]

- gremo

@Yasir Arsanukaev：已修复，谢谢。 - gremo

编辑了第一篇帖子... - gremo

您可以将您的改进作为评论收集和报告，然后编辑问题，以便包括这些评论。如果您编辑问题8次，则会变成社区维基。CW不会产生声望。因此，请勿经常编辑您的帖子。 - YasirA

1

我不确定，但也许 where 语法会适合您的需求 :-) http://freebsd.pastebin.com/QX1Bi0sj - YasirA

@Yasir Arsanukaev：很好的起点，谢谢。 - gremo

@Gremo 为什么你说：“尽可能避免使用外部函数，只使用匿名函数。”？任何“外部”函数都可以内联为匿名函数，但这会使它变得丑陋不堪。 - Dan Burton

2个回答

1

怎么样呢？

ishsymmetric qt = qt == fliph qt

- Darius Bacon

你的意思是 ishsymmetric qt = equals qt (fliph qt) 吗？ - gremo

@Gremo 我相当确定 equals 方法已经变得不必要了... 因为 QT 已经派生了 Eq。 - Dan Burton

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- YasirA · Accepted Answer

类似这样：

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)

但是语法优化是可能的。 :-/