instancji Monada do binarnego drzewa

Question

Zbudowałem binarne drzewo z:

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

Jak mogę dokonać monada instancję klasy typu na tym drzewie? I czy mogę to zrobić?

próbuję:

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

ale nie mogę zrobić (>> =) na węźle x lewo prawo.

Dziękuję.

Answer 1

Nie ma (dobrej) monady dla dokładnie opisanego typu. Wymagałoby to ponownego zrównoważenia drzewa i połączenia ze sobą pośrednich drzew, które są generowane przez wiązanie, i nie można przywrócić równowagi na podstawie jakichkolwiek informacji w "a", ponieważ nic nie wiesz o tym.

Jednak istnieje podobna struktura drzewa

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

który przyznaje monady

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

Rozmawiałem o tym i innych strukturach drzewiastych a year or two back at Boston Haskell jako lead-in, aby mówić o drzewach palców. Slajdy mogą być pomocne w badaniu różnic między liściastymi a tradycyjnymi drzewami binarnymi.

Powodem, dla którego powiedziałem, że nie ma dobrej monady, jest to, że jakakolwiek taka monada musiałaby umieścić drzewo w formie kanonicznej dla danej liczby wpisów, aby uchwalić ustawy monadowe lub rozważyć pewne obawy o równowagę poprzez nieumieszczenie konstruktorów dla użytkownika końcowego, ale wykonanie tego pierwszego wymagałoby znacznie bardziej rygorystycznej zmiany kolejności niż na przykład z AVL lub ważonego drzewa.