带有 Set 的 Haskell Ord 实例

Question

我有一些代码想用来将边附加到 Node 数据结构：

import Data.Set (Set)
import qualified Data.Set as Set

data Node = Vertex String (Set Node)
    deriving Show

addEdge :: Node -> Node -> Node
addEdge (Vertex name neighbors) destination
    | Set.null neighbors    = Vertex name (Set.singleton destination)
    | otherwise             = Vertex name (Set.insert destination neighbors)

但是，当我尝试编译时，我收到此错误：

No instance for (Ord Node)
      arising from a use of `Set.insert'

据我所知，Set.insert 除了一个值和一个集合之外什么都不需要将其插入。这个命令是什么？

Answer 1

在 GHCi 中：

> import Data.Set
> :t insert
insert :: (Ord a) => a -> Set a -> Set a

所以是的，它确实需要 Ord。至于Ord的含义，它是有序值的类型类。在本例中这是必需的，因为 Data.Set 使用搜索树，因此需要能够比较值以查看哪个较大或它们是否相等。

几乎所有标准内置数据类型都是 Ord 的实例，列表、元组、Maybe 等都是 Ord< 的实例。 /code> 当它们的类型参数是时。当然，最值得注意的例外是函数，其中无法定义合理的排序（甚至相等）概念。

在许多情况下，您可以在声明后使用 deriving 子句自动为您自己的数据类型创建类型类的实例：

data Foo a = Foo a a Int deriving (Eq, Ord, Show, Read)

对于参数化类型，自动派生取决于类型参数也是一个实例，如下所示列表、元组等就是这种情况。

除了 Ord 之外，一些重要的类型类还有 Eq（相等比较，但不能小于/大于）、Enum（可以枚举以下值的类型） ，例如计数Integer）和Read/Show（使用字符串进行简单的序列化/反序列化）。要了解有关类型类的更多信息，请尝试Real World Haskell 中的本章，或者，更全面的概述，有维基百科文章。

Answer 2

Haskell 集基于搜索树。为了将元素放入搜索树中，必须给出元素的排序。您可以像派生 Show 一样将其添加到数据声明中来派生 Ord，即：

data Node = Vertex String (Set Node)
   deriving (Show, Eq, Ord)

您可以通过 Data.Set.insert 的签名看到 Ord 的要求

(Ord a) => a -> Set a -> Set a

(Ord a) =>(Ord a) => 建立了一个约束，即 a 存在类型类 Ord 的实例。 有关类型类的部分位于 haskell 教程 给出了更全面的解释。