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

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

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

This post Heinrich Apfelmus 的著作很好地展示了这种方法。他定义

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

所以 a 类型的值只是在叶子上，但是所有节点(内部节点和叶子节点)都由 v 类型注释，并且只需选择各种 monoids对于 v，我们得到了不同的有趣数据结构。