Haskell Ord экземпляр с Set

Question

У меня есть некоторый код, который я хотел бы использовать, чтобы добавить ребро к структуре данных узла:

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 (типы можно перечислить значения, такие как подсчет Integer с), и Read/Show (простой сериализации/десериализации со строками). Чтобы узнать больше о типах классов, попробуйте this chapter in Real World Haskell или, для более общего обзора, есть a Wikipedia article.

Answer 2

Наборы Haskell основаны на дереве поиска. Чтобы поместить элемент в дерево поиска, необходимо указать порядок над элементами. Вы можете получить Ord так же, как вы производный Показать, добавив его в декларации данных, а именно:

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

Вы можете увидеть требование Ord подписью Data.Set.insert

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

Часть (Ord a) => устанавливает ограничение на наличие экземпляра класса Ord для a. section on type classes в haskell tutorial дает более подробное объяснение.