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

Я построил двоичное дерево с помощью:

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

Но я не могу сделать ( → =) для Node x слева направо.

Спасибо.

Ответы

Ответ 1

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

Однако существует аналогичная древовидная структура

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)

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

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