是否可以在Haskell中将Set表示为Tree? [英] Is it possible to represent Set as Tree in Haskell?

问题描述

我正在阅读纯粹的功能数据结构"，并试图解决它们在haskell中进行的练习.

I'm reading Purely Functional Data Structres and trying to solve exercises they give in haskell.

我已经以标准方式定义了 Tree data Tree a = Empty |节点a(树a)(树a)我想将 Set 定义为 Tree ，其中节点是 Ord 的实例.有没有办法在Haskell中表达这一点?像 type Set = Tree Ord 之类的东西，还是我每次想将某些数据结构表示为树时都认为要重新实现树?

I've defined Tree in a standard way data Tree a = Empty | Node a (Tree a) (Tree a) I'd like to define Set as Tree where nodes are instance of Ord. Is there a way to express this in Haskell? Something like type Set = Tree Ord or I deemed to reimplement tree every time I want express some data structure as tree?

推荐答案

您是否打算将该树用作二进制搜索树(BST)?为此，您需要执行所有操作来保留强大的BST属性:对于BST中的每个 Node 构造函数，左子树中的所有 Node 所包含的元素都小于在当前 Node 中一个，右子树中的所有 Node 都包含更大的元素.

Do you intend to use the tree as a binary search tree (BST)? For that to work, you need all operations to preserve the strong BST property: for each Node constructor in the BST, all Nodes in the left subtree contain elements less than the one in the current Node, all Nodes in the right subtree contain elements greater.

您绝对需要保留该财产.一旦不再正确，所有进一步的BST操作都会失去正确性保证.这一结论具有后果.您不能公开该类型的构造函数.您不能公开不保留BST属性的操作.

You absolutely need to preserve that property. Once it's no longer true, all further BST operations lose correctness guarantees. This conclusion has consequences. You can't expose the constructors of the type. You can't expose operations to work on it that don't preserve the BST property.

因此，对集合进行操作的每个操作都必须有权访问 Ord 实例，该实例受节点约束.(好吧，除了几个特殊情况，例如检查集合是否为空或创建单例集合，这些都不必处理子项的顺序.)

So every operation that operates on a set needs to have access to the Ord instance for the type constrained in the node. (Well, other than a couple special cases like checking if a set is empty or creating a singleton set, which never have to deal with the order of children.)

到那时，您可以将树类型与其他用途完全共享什么?您无法共享操作.您不能使用构造函数.剩下，好吧..没什么用.您无法共享类型的名称，而无法使用它做任何事情.

At that point, what exactly can you share about the tree type with other uses? You can't share operations. You can't use the constructors. That leaves, well.. nothing useful. You could share the name of the type with no ways to do much of anything with it.

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

So, no.. You can't share a binary search tree data type with other uses that just seek an arbitrary binary tree. Attempting to do so just results in a broken BST.

这篇关于是否可以在Haskell中将Set表示为Tree?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！