带有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它们是类型参数的实例.当然,最值得注意的例外是函数,其中不能定义合理的排序概念(甚至是相等).

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

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

对于参数化类型,自动派生依赖于类型参数也是一个实例,就像列表,元组等一样.

此外Ord,一些重要的类型类是Eq(相等比较,但不小于/大于),Enum(可以枚举值的类型,例如计数Integers)和Read/ Show(使用字符串的简单序列化/反序列化).要了解有关类型类的更多信息,请在Real World Haskell中尝试本章,或者,对于更一般的概述,有一篇维基百科文章.