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?
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.