Haskell Ord instance with a Set

Question

I have some code that I would like to use to append an edge to a Node data structure:

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)

However when I try to compile I get this error:

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

As far as I can tell, Set.insert expects nothing but a value and a set to insert it into. What is this Ord?

Answer 1

Haskell sets are based on a search tree. In order to put an element in a search tree an ordering over the elements must be given. You can derive Ord just like you are deriving Show by adding it to your data declaration, i.e.:

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

You can see the requirement of Ord by the signature of Data.Set.insert

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

The part (Ord a) => establishes a constraint that there is an instance of the typeclass Ord for a. The section on type classes in the haskell tutorial gives a more thorough explanation.

Answer 2

In GHCi:

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

So yes, it does expect Ord. As for what Ord means, it's a type class for ordered values. It's required in this case because Data.Set uses a search tree, and so needs to be able to compare values to see which is larger or if they're equal.

Nearly all of the standard built-in data types are instances of Ord, as well as things like lists, tuples, Maybe, etc. being instances of Ord when their type parameter(s) are. The most notable exception, of course, are functions, where no sensible concept of ordering (or even equality) can be defined.

In many cases, you can automatically create instances of type classes for your own data types using a deriving clause after the declaration:

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

For parameterized types, the automatic derivation depends on the type parameter also being an instance, as is the case with lists, tuples, and such.

Besides Ord, some important type classes are Eq (equality comparisons, but not less/greater than), Enum (types you can enumerate values of, such as counting Integers), and Read/Show (simple serialization/deserialization with strings). To learn more about type classes, try this chapter in Real World Haskell or, for a more general overview, there's a Wikipedia article.