Arbitrary class constraints when implementing type classes in Haskell

Question

I'm trying to implement a simple Set in Haskell, and am getting stuck with how to express class constraints for the elements it contains.

The Set type class is fairly simple:

class Set s where
  empty    :: s a
  isEmpty  :: s a -> Bool
  insert   :: s a -> a -> s a
  contains :: s a -> a -> Bool

A trivial implementation of a Set is a binary search tree:

data BinarySearchTree a = Node a (BinarySearchTree a) (BinarySearchTree a) | Leaf

I'm getting somewhat stuck when it comes to declaring the correct class constraints, however:

• Set requires, at the very least, the ability to decide whether two elements are equal - its values need to have an instance of Eq.
• BinarySearchTree requires its elements to have an instance of Ord, since each node needs to have the smaller element on the left and the bigger on the right.

The first, simple solution is to update Set's signature to require a to have an instance of Eq:

class Set s where
  empty    :: Eq a => s a
  isEmpty  :: Eq a => s a -> Bool
  insert   :: Eq a => s a -> a -> s a
  contains :: Eq a => s a -> a -> Bool

Implementing an instance of Set for BinarySearchTree is not a problem: Ord implies Eq, so I can "override' the class constraints.

What if, however, BinarySearchTree required some exotic class contraints, ones that are entirely incompatible with Eq? How do I express these and keep the type checker happy?

The only way I can think of is to add a class constraint on BinarySearchTree, something like:

data Ord a => BinarySearchTree a = Node a (BinarySearchTree a) (BinarySearchTree a) | Leaf

Unfortunately, this does not seem to satisfy the type checker: even though the declaration guarantees that BinarySearchTree must contain elements with an Ord instance, this constraint doesn't seem to carry over to functions that use BinarySearchTree - it's as if the class constraint only applied to the data constructors, but were then forgotten about.

What am I missing? Is there an elegant solution for what I'm trying to do, or even a solution at all?

Answer 1

You're asking about a well-known problem in Haskell: how to define a type class such that instances of the type class can define the type class constraints they require for the type class's operations. This problem often appears on discussion forums in the form of the question "Why is Data.Set not an instance of Functor?" and then the problem is that Data.Set has a map function with an additional Ord constraint:

Data.Set.map :: Ord b => (a -> b) -> Set a -> Set b 

while Functor's fmap method looks like

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Since a few years, solutions to the problem exist. One solution combines the relatively new extension ConstraintKinds with TypeFamilies. For your example, it would amount to something like this:

class Set s where
  type SetCt s a :: Constraint
  empty    :: s a
  isEmpty  :: s a -> Bool
  insert   :: Ct a => s a -> a -> s a
  contains :: Ct a => s a -> a -> Bool

The instance for BinarySearchTree would then look like

instance Set BinarySearchTree where
  type SetCt BinarySearchTree a = Ord a
  ...

Here is a blog post by Dominic Orchard which explains these ideas in a bit more detail.