是否有任何有效的数据结构来表示除二进制搜索树之外的Set

Question

众所周知，在Haskell中，一组元素由Data.Set模块中的二叉搜索树表示，这是有效的。但是，大多数操作都要求elememt是Ord类的实例。

但是，一般集不需要它的元素作为Ord的实例。由于set是没有重复元素的地方，因此它的元素是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

Traceback（最近一次调用最后一次）：

文件“”，第1行，在模块中

x <= y

TypeError：'Fruit'和'Fruit'实例之间不支持'<='

所以我想知道Haskell中是否有一些有效的数据结构可用于表示Set但不需要Ord类。

Answer 1

Python是作弊。 All values in Python are hashable and set() is just a dictionary with no value.

Python可以将其作为动态类型语言的副作用。允许Python跟踪变量类型的相同机制也可以很容易地对它们施加psudo排序。

Haskell作为静态类型语言，通常是具有第一类函数的静态类型语言，不能为数据类型发明任意排序。因此Data.Set要求Ord有效。如果没有订购，则为集合添加新值将变为O（n）。