

Join them; it only takes a minute:

Sign up
Join the Stack Overflow community to:
  1. Ask programming questions
  2. Answer and help your peers
  3. Get recognized for your expertise

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?

share|improve this question
Have a look at this stuff. They're doing something similar with monads. – phg Sep 19 '12 at 15:24
Thank you very much for link, ConstraintKind is really interesting stuff! – roman-kashitsyn Sep 19 '12 at 15:53
Btw, does findMin really require an Ord instance? – yairchu Sep 19 '12 at 21:40
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 Sep 19 '12 at 22:07

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:

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:


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


Here we need to provide an Ord instance as well.

share|improve this answer
Thank you, I got it working, I've prepared small sample how to do that here: It looks strange for me, but we can't just use constraints in type declaration like this: newtype Ord a => ListHeap a = LH [a]. This just doesn't work with Foldable instance. We really have to use GADTs extension with pattern matching. Thank you very much for your answer! – roman-kashitsyn Sep 19 '12 at 20:24
@roman-kashitsyn: Yeah, there is/was a syntax like that for regular data types, but it didn't do the same thing and was a completely useless misfeature and will probably be removed from the language standard eventually (unless it already was and I've forgotten). – C. A. McCann Sep 19 '12 at 23:32

Take a look at keys library on Hackage. Check if its FoldableWithKey type class is what you need.

share|improve this answer

Your Answer


