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?

It seems that one of my points is incorrect: I was certain I had managed to do the whole "Eq on Set, Ord on BinarySearchTree" thing but I can't get that to compile anymore.... — Nicolas Rinaudo
Note: this question is related to another one: stackoverflow.com/questions/25345055/…. Not sure if it's close enough to be considered a duplicate... — Dominique Devriese
I'm not sure they qualify as duplicates, even though they do both seem to come from the same root problem. Either way is fine by me, and I would not be offended for my question to be closed as a duplicate. — Nicolas Rinaudo

Dominique Devriese Dominique Devriese · Accepted Answer · 2014-08-21T09:28:57

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.

Arbitrary class constraints when implementing type classes in Haskell

2 Answers