Search code examples
haskellderiving

Why is the key in Data.Map constrained to class Ord?

Suppose I define a simple type like this:

data Object = House | Table | Book

To be able to use Objects as keys for a map, the type has to be derived from Eq and Ord:

data Object = House | Table | Book deriving (Eq, Ord)

What is the reason for this restriction? Why do the keys of a map need to be orderable?

Solution

  • Data.Map offers O(log N) complexity on most operations (insertion, lookup, deletion, ...). It can do that since internally it uses a balanced search tree. That, in turn, requires an ordering relation on keys, hence the Ord constraint. Eq is a superclass of Ord, so that must be provided as well.

    With only Eq we can't be as efficient on -say- lookup, since the best we can do in such case is to perform a linear search, which is O(N).

    Without Eq, we can not perform lookup at all since we have no way to compare already inserted keys with the key to look up.