二叉树的 Monad 实例 [英] Monad instance for binary tree

问题描述

我用以下方法构建了二叉树:

I built binary tree with:

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

如何为这棵树创建 Monad 类型的类实例?我可以不做吗?

How can i make Monad type class instance for this tree? And can i make it on not?

我尝试:

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

但我不能为节点 x 左右创建 (>>=).

But i can't make (>>=) for Node x left right.

谢谢.

推荐答案

对于您刚刚描述的类型，完全没有(好的)monad.它需要重新平衡树并将绑定生成的中间树合并在一起，并且您无法根据 'a' 中的任何信息重新平衡，因为您对此一无所知.

There is no (good) monad for the type you just described, exactly. It would require rebalancing the tree and merging together the intermediate trees that are generated by the bind, and you can't rebalance based on any information in 'a' because you know nothing about it.

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

However, there is a similar tree structure

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

它承认一个 monad

which admits a monad

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

我在波士顿 Haskell 一两年后作为领导谈到了这个和其他树结构一两年在谈论手指树.那里的幻灯片可能有助于探索多叶树和传统二叉树之间的区别.

I talked about this and other tree structures a year or two back at Boston Haskell as a lead-in to talking about finger trees. The slides there may be helpful in exploring the difference between leafy and traditional binary trees.

我说没有好的 monad 的原因是，对于给定数量的条目，任何此类 monad 都必须将树置于规范形式中，以通过 monad 定律或通过不暴露构造函数来商出一些平衡问题对最终用户而言，但执行前者需要比从 AVL 或加权树中获得的更严格的重新排序.

The reason I said there is no good monad, is that any such monad would have to put the tree into a canonical form for a given number of entries to pass the monad laws or quotient out some balance concerns by not exposing the constructors to the end user, but doing the former would require much more stringent reordering than you get for instance from an AVL or weighted tree.

这篇关于二叉树的 Monad 实例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！