二叉树的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.

谢谢.

推荐答案

您刚才描述的类型没有(好的)单子.这将需要重新平衡树并将合并生成的中间树合并在一起，并且您无法基于'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.

但是，有类似的树结构

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)

我谈到了这种树木结构和其他树木结构在一两年前回到波士顿·哈斯克尔(Boston 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屋！