二叉树的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 左右子节点做(>>=)操作。

谢谢。

- 0xAX

---

这取决于你希望 join :: Tree (Tree a) -> Tree a 如何运作。 - dave4420

正如@dave4420所说，考虑使用join。您可以让join进行替换，然后Tree将成为一个单子。 - augustss

Answer 1

刚才描述的类型并没有一个（好的）单子。这需要重新平衡树并合并由bind生成的中间树，而您无法根据'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)

我曾在一两年前的波士顿Haskell会议上谈到了这个和其他树形结构，作为引入讨论finger trees的铺垫。那里的幻灯片可能有助于探索叶状和传统二叉树之间的区别。

我说没有好的monad的原因是，任何这样的monad都必须将树放入给定条目数量的规范形式中，以通过monad法则或通过不向最终用户公开构造函数来消除某些平衡问题的商数，但是做前者需要比您从AVL或加权树中获得的更严格的重新排序。

- Edward Kmett

---

我不理解二叉树 Bin (Tree a) (Tree a)。它的根节点没有值吗？ - dehq

@dehq 正确：这种形式的树只有装饰叶子，而不是沿着下降路径的节点。你可以制作一个带有装饰节点的树，但那并不能在这些装饰上形成（自由）单子。链接的幻灯片更多地讨论了叶状树和节点值树之间的权衡以及不同的用途。 - Edward Kmett