Слишком много совпадений шаблонов, чтобы записать для Quadtrees? - PullRequest
Новая
       22

Слишком много совпадений шаблонов, чтобы записать для Quadtrees?

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

Представьте себе quadtree , определенное следующим образом: 

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

bad1 = Q u u u u where u = C 255
bad2 = Q (C 0) (C 255) (Q u u u u) (C 64) where u = C 255

Конструктор позволяет создавать не правильно сформированные quadtree.bad1 должно быть просто C 255, а bad2 также недопустимо, потому что его нижнее правое квадродерево (по той же причине оно должно быть Q (C 0) (C 255) (C 244) (C 64).

Пока все хорошо. Проверка его хорошоформальность - это просто вопрос рекурсивной проверки своих внутренних четырех деревьев. базовый случай - это когда все внутренние четыре дерева имеют листьев , при этом все цвета не должны быть равны всем. 

wellformed :: (Eq a, Show a) => QT a -> Bool
wellformed (Q (C c1) (C c2) (C c3) (C c4)) = any (/= c1) [c2, c3, c4]
wellformed (Q (C c1) (C c2) se (C c4))     = valid se
-- continue defining patters to match e.g Q C C C, C Q Q C, and so on...

Вопрос : Можно ли не вводить все совпадения для всех возможных комбинаций листьев и четырех деревьев?

Пожалуйста, будьте терпеливы, если мой вопрос довольно странный, ноэто мой второй день - Хаскелл-безукоризненное обучение!

1 Ответ

4 голосов
/ 04 февраля 2011

Nevermind ... 

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

РЕДАКТИРОВАТЬ : или даже лучше: 

wellformed :: (Eq a, Show a) => QT a -> Bool
wellformed (C _) = True
wellformed (Q (C c1) (C c2) (C c3) (C c4)) = any (/= c1) [c2, c3, c4]
wellformed (Q nw ne se sw) = all wellformed [nw, ne, se, sw]

РЕДАКТИРОВАТЬ : обратите внимание, что привязки неправильно , должны быть: NW NE SW SE !!!

...