我应该如何在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

前者肯定更好，因为它可以表示任意二叉树，而后者则不然。例如，第二个版本不能表示：

Answer 2

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

另一方面，如果您的树充当不受约束元素的容器，而树的形状不依赖于它们，则将值放在叶子上更有意义。

Heinrich Apfelmus 的

This post 很好地展示了这种方法。他定义

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

所以 a 类型的值只是在叶子上，但是所有节点（内部节点和叶子节点）都按类型 v 注释，并且只需为 [ 选择各种 monoids =12=]，我们得到了不同的有趣的数据结构。

Answer 3

正如@PetrPudlák 所说，这取决于。前者更适合搜索树。然而，后一个版本是一个（免费的）monad，这也很有用：

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

(>>=)运算符对应"substitution at the leaves".

Functor 和 Applicative 实例也很有用。随着 GHC 7.10 的发布，当您定义 Monad 时，它们已成为强制性的。我们可以使用 monad 函数来定义它们：

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

Answer 4

我认为后一种几乎没有用，因为它可以扁平化为（非空）列表，唯一的区别是分支结构。然而，这仍然很难在运行时进行分析，因为内部节点没有携带额外的信息；当你看到一个分支时，你不能对它的两个子树中的任何一个说任何话。要区分它们，您必须遍历它们并从根本上消除我们更喜欢树的 O(log n) 复杂性。

如果有人找到这种数据结构的用例，请告诉我。

How should I define a binary tree in Haskell?