haskell - propia - Instancia de mónada para árbol binario

mapa conceptual de los principales problemas de la filosofia de leibniz y espinoza

Question

Construí un árbol binario con:

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

¿Cómo puedo hacer una instancia de clase de tipo Monad para este árbol? ¿Y puedo hacerlo en no?

lo intento:

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

Pero no puedo hacer (>> =) para Nodo x izquierda derecha.

Gracias.

Answer 1

No hay una (buena) mónada para el tipo que acaba de describir, exactamente. Requeriría reequilibrar el árbol y fusionar los árboles intermedios que genera el enlace, y no puede rebalancearse en base a ninguna información en ''a'' porque no sabe nada al respecto.

Sin embargo, hay una estructura de árbol similar

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

que admite una mónada

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

Hablé sobre esta y otras estructuras de árboles uno o dos años atrás en Boston Haskell como una guía para hablar sobre los árboles de dedos. Las diapositivas allí pueden ser útiles para explorar la diferencia entre árboles binarios frondosos y tradicionales.

La razón por la que dije que no hay una buena mónada es que cualquier mérada tendría que poner el árbol en una forma canónica para que un número dado de entradas aprobara las leyes de la mónada o el cociente fuera de algunos problemas de equilibrio al no exponer a los constructores al final usuario, pero hacer lo primero requeriría una reordenación mucho más estricta que la que obtendría, por ejemplo, de un AVL o un árbol ponderado.