二进制树的Monad实例

Question

我用以下内容构建二叉树:

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 

但我不能让(x = =)节点x左右.

谢谢.

Answer 1

确切地说,你刚才描述的类型没有(好)monad.它需要重新平衡树并将绑定生成的中间树合并在一起,并且您无法根据'a'中的任何信息进行重新平衡,因为您对此一无所知.

但是,有一个类似的树结构

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

承认一个monad

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

我在波士顿哈斯克尔一年或两年后谈到了这个和其他树木结构作为谈论手指树的引导.那里的幻灯片可能有助于探索绿叶和传统二元树之间的差异.

我说没有好的monad的原因是,任何这样的monad都必须将树放入规范形式,以便给定数量的条目传递monad法则或通过不将构造函数暴露到最终来解决一些平衡问题用户,但做前者需要比从AVL或加权树获得的更严格的重新排序.