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]