Type parameters constraints for instances of typeclasses with kind * -> *

Question

Suppose I have Heap a type where Heap is type constructor of kind * -> *. Many basic operations on heap require the a type to be an instance of Ord type class.

data Heap a = ...

findMin :: Ord a => Heap a -> a
deleteMin :: Ord a => Heap a -> Heap a

I want to declare my Heap type as an instance of Foldable type class as soon as a type parameter is an instance of Ord type class (it will be easy to express via findMin and deleteMin functions).

This kind of relation can be easely expressed when we dealing with type classes that require type of kind *, like Show:

instance Show a => Show (Heap a) where
    show h = ...

But I have problems with declaration of Foldable:

instance Foldable Heap where
    -- Ouch, there is no `a` type parameter to put the constraint on!
    foldr f z h = ...

Is it possible to put constraint on a type parameter in such instance declaration?

Have a look at this stuff. They're doing something similar with monads. — phipsgabler
Thank you very much for link, ConstraintKind is really interesting stuff! — roman-kashitsyn
Some implementations (like the slow list-based one I showed below) don't require Ord constraint on findMin, but some of them (like the SkewBinominalHeap described by Okasaki) require that constraint. I suppose in real life Heap should be a type class with the Ord constraint on findMin. — roman-kashitsyn

C. A. McCann C. A. McCann · Accepted Answer · 2012-09-19T16:41:22

In general, no, when the type constructor itself is given the instance, there's no way to constrain the types it's applied to. Mostly this is a good thing, since it ensures that e.g. Functor instances are truly agnostic about their element type, which helps keep nice and predictable behavior nice and predictable.

Sometimes it's an annoyance instead, and the most common example is indeed needing an Ord constraint for a sorted data structure that could otherwise be a nice, well-behaved instance.

There are some experimental techniques involving stuff like constraint kinds, but in your specific case there's already a viable solution. If you look at the definition of Foldable, it says that only foldMap or foldr need to be implemented, so we'll consider those. Note the types:

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b

In both cases, the type with a Foldable instance only appears once, as an argument to the function. Because of this, you can use GADTs with an Ord constraint:

data Heap a where
    Heap :: (Ord a) => ...

By doing this, you'll need an Ord instance any time you create a Heap value, even an empty heap; but when you receive a Heap value, pattern matching on it will bring the Ord instance back into scope--even inside the Foldable instance!

Note that this doesn't help in many other situations:

fmap :: (Functor f) => (a -> b) -> f a -> f b

Here we can get an Ord instance on a, but we'd also need one for b, which isn't possible.

return :: (Monad m) => a -> m a

Here we need to provide an Ord instance as well.

Type parameters constraints for instances of typeclasses with kind * -> *

2 Answers