我应该如何在Haskell中定义二叉树？

Question

在Haskell中,可以用以下两种方式之一定义二叉树:

data Tree a = Empty | Branch a (Tree a) (Tree a)

要么

data Tree a = Leaf a | Branch (Tree a) (Tree a)

选择一个优于另一个有什么好处？在哪种情况下,一个树结构比另一个更好？

Answer 1

这在很大程度上取决于您的应用 如果树的形状由元素确定,则前一个定义更好,例如,如果您有一个平衡的二叉树:

另一方面,如果您的树充当不受约束的元素的容器,其中树的形状不依赖于它们,则将值放入叶子更有意义.

Heinrich Apfelmus的这篇文章很好地展示了这种方法.他定义

data Tree v a = Leaf   v a
              | Branch v (Tree v a) (Tree v a)

因此,类型的值a都只是在叶子,但所有节点(包括内部和叶)按类型注解v,只是通过选择不同类群的v,我们得到不同的有趣的数据结构.

Answer 2

正如@PetrPudlák所说,这取决于.前者更适合搜索树.但是,后一个版本是(免费)monad,它也可以是有用的:

instance Monad Tree where
    return = Leaf
    Leaf x >>= f = f x
    Branch t1 t2 >>= f = Branch (t1 >>= f) (t2 >>= f)

该(>>=)操作相当于"在叶替代".

在Functor和Applicative实例是有用的.使用GHC 7.10时,它们在您定义时已成为必需项Monad.我们可以使用monad函数来定义它们:

instance Functor Tree where fmap = Control.Monad.liftM
instance Applicative Tree where pure = return; (<*>) = Control.Monad.ap