Алгоритм проверки горизонтальной симметрии дерева? - PullRequest
3 голосов
/ 05 февраля 2011
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]

Ответы [ 2 ]

1 голос
/ 05 февраля 2011

Как насчет

ishsymmetric qt = qt == fliph qt
1 голос
/ 05 февраля 2011

Что-то вроде:

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)

Но возможны синтаксические оптимизации. : - /

...