Экземпляр монады для двоичного дерева - PullRequest
Новая
       24

Экземпляр монады для двоичного дерева

25 голосов
/ 23 июля 2011

Я построил двоичное дерево с: 

data Tree a = Empty 
              | Node a (Tree a) (Tree a)
              deriving (Eq, Ord, Read, Show)

Как сделать экземпляр класса Monad для этого дерева? И могу ли я сделать это на нет?

я стараюсь: 

instance Monad Tree where
    return x = Node x Empty Empty 
    Empty >>= f = Empty
    (Node x Empty Empty) >>= f = f x

Но я не могу сделать (>> =) для узла х слева направо.

Спасибо.

1 Ответ

35 голосов
/ 23 июля 2011

Нет (хорошей) монады для типа, который вы только что описали, точно.Это потребует перебалансировки дерева и слияния промежуточных деревьев, сгенерированных связыванием, и вы не сможете перебалансировать, основываясь на любой информации в «а», потому что вы ничего не знаете об этом.

Однако, естьпохожая древовидная структура 

data Tree a = Tip a | Bin (Tree a) (Tree a)

, которая допускает монаду 

instance Monad Tree where
   return = Tip
   Tip a >>= f = f a
   Bin l r >>= f = Bin (l >>= f) (r >>= f)

Я говорил об этой и других древовидных структурах год или два назад в Бостонском Хаскеле какВступление к разговору о пальцах.Слайды могут быть полезны для изучения различий между листовыми и традиционными бинарными деревьями.

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

...