如何在Haskell中定义无序集合

Question

想知道如何在Haskell中定义一个无序的组/集合，其中“集合”是指它可以具有相同元素的许多副本，而这些项是无序的。我知道ListHaskell 中的数据类型，但这是固有的顺序。我想查看无序集合/组/列表的定义。

Answer 1

我会这样定义

import qualified Data.Map.Lazy as Map

type MultiSet' a = Map.Map a Int 

只是从类型a到的映射Int。在数学上它会是这样的˚F：小号 - > ñ。您放入其中的元素必须是可排序的，这是因为的基础结构Map是由二叉树定义的。这应该不成问题，因为使用数据结构时您可以将其忘记。请参阅Data.Map的非常详细的文档以获取处理我们的函数的信息MultiSet'。

现在已经有了定义和实现的定义，它称为MultiSet。您也可以浏览到其源代码，在那里他们看到它们以几乎相同的方式定义了它们（它们使用了地图的严格版本）。

或者，您可以使用一个哈希图，它看起来像这样：

import qualified Data.HashMap.Lazy as Map

type MultiSet'' a = Map.HashMap a Int 

放入其中的元素不必是可排序的，而是可哈希的。