除了二进位搜索树之外，是否有有效的数据结构来表示集合？
提问于 2019-03-12 22:20:25
我们知道，在Haskell中，一组元素由Data.Set模块中的二进制搜索树表示，这是一种有效的方法。但是，大多数操作都要求elememt是Ord类的一个实例。
但是，一般集合不需要它的元素作为Ord的实例。因为集合是没有重复元素的地方，所以它的元素作为Eq类的一个实例就足够了。
在Haskell中，我只能想到一个链表的实现，就像默认的[a]一样，但是单链列表的效率不如BST，而BST需要Ord类。
顺便说一句，在Python中，set类不需要它的元素是可排序的。只有定义了__eq__和__ne__ (这是Haskell的Eq类的silimar )就足够了，例如：
class Fruit:
def __init__(self, name):
self.name = name.title()
def __repr__(self):
return self.name
def __eq__(self, other):
return self.name == other.name # defines the equality operation
def __ne__(self, other):
return self.name != other.name # defines the unequality operation
def __hash__(self):
return hash(self.name) # so that Fruit instance can be an element of a set?：X=水果(‘苹果’) Y=水果(‘苹果’) Z=水果(‘Apple’) ?：{x，y，z} {苹果] ?：x <= y 回溯(最近一次调用)： 文件""，第1行，在模块中 X <= y TypeError：“水果”和“水果”实例之间不支持“<=”
因此，我想知道Haskell中是否有一些有效的数据结构可以用来表示Set，但不需要Ord类。
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-03-12 23:12:06
Python在作弊。 is just a dictionary with no value.
Python可以作为动态类型化语言的一个副作用来解决这个问题。让Python跟踪it变量类型的机器也使得在它们上强制执行psudo排序变得很容易。
Haskell作为一种静态类型化语言，尤其是具有一流函数的静态类型化语言，不可能为数据类型创造任意排序。因此，Data.Set要求Ord是高效的。在没有排序的情况下，向集合添加一个新值就变成了O(n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55135591
复制相关文章
腾讯云开发者
