是否可以在 Haskell 中将 Set 表示为 Tree？

Question

我正在阅读 Purely Functional Data Structres 并尝试解决他们在 haskell 中提供的练习。

我已经用标准方式定义了 Tree data Tree a = Empty | Node a (Tree a) (Tree a) 我想将 Set 定义为 Tree，其中节点是 Ord 的实例。有没有办法用 Haskell 表达这个？像 type Set = Tree Ord 或者我认为每次我想将一些数据结构表达为树时都重新实现树？

Answer 1

这正是 containers 库中的 Data.Set 模块所做的：

http://hackage.haskell.org/package/containers-0.5.10.2/docs/src/Data-Set-Internal.html#Set

您可以尝试阅读它的实现。 type Set = Tree Ord 如果您不使用某些外来语言扩展，则无法编译。但您可能不想使用它们，而是对以下函数更感兴趣：

insert :: Ord a => a -> Tree a -> Tree a
find   :: Ord a => a -> Tree a -> Maybe a
delete :: Ord a => a -> Tree a -> Tree a

这就是类型 类 的用途。

Answer 2

您打算将该树用作二叉搜索树 (BST) 吗？为此，您需要所有操作来保留强 BST 属性：对于 BST 中的每个 Node 构造函数，左子树中的所有 Node 包含的元素小于当前 Node，右子树中的所有 Node 都包含更大的元素。

您绝对需要 来保留 属性。一旦它不再为真，所有进一步的 BST 操作将失去正确性保证。这个结论是有后果的。您不能公开该类型的构造函数。您不能公开不保留 BST 属性.

的操作。

因此，对集合进行操作的每个操作都需要访问节点中受限类型的 Ord 实例。 （好吧，除了一些特殊情况，例如检查集合是否为空或创建单例集合，它们永远不必处理子项的顺序。）

到时候，关于这种树种，您能具体分享些什么给其他人使用呢？你不能共享操作。您不能使用构造函数。剩下的，嗯.. 没什么用。您可以共享类型的名称，但无法对其进行任何操作。

所以，不.. 您不能与其他只寻找任意二叉树的用途共享二叉搜索树数据类型。尝试这样做只会导致 BST 损坏。