This paper describes a flexible type system which combines overloading and higher-order polymorphism in an implicitly typed language using a system of constructor classes -- a natural generalization of type classes in Haskell.
We present a wide range of examples which demonstrate the usefulness of such a system. In particular, we show how constructor classes can be used to support the use of monads in a functional language.
The underlying type system permits higher-order polymorphism but retains many of many of the attractive features that have made the use of Hindley/Milner type systems so popular. In particular, there is an effective algorithm which can be used to calculate principal types without the need for explicit type or kind annotations. A prototype implementation has been developed providing, amongst other things, the first concrete implementation of monad comprehensions known to us at the time of writing.