Emulating closed type classes with closed type families
Haskell actually implements two languages: The value-level language, and a more limited type-level language that is evaluated at compile time. GHC’s support for type-level programming is quite powerful. This recent post e.g. shows how to do a type-level
if amongst things.
One useful property of closed type families is that they are evaluated in order, like pattern matching in function bodies. We start with a simple example that matches a type to a colour:
After loading this code into ghci I can test the explicitly specified
λ :load closed.hs
But, and this is the important property, if no type matches
Colour falls through to the general
ty type, Grey:
λ :kind! (Colour Bool)
In Haskell type classes are open, i.e. anyone can implement a new instance for their type. This means that the compiler always needs to be able to decide which instance to pick. There is no way of “falling through” to a most generic instance like we did in the closed type family. We can try specifing a generic instance matching all types
When loading the code above we get:
OVERLAPPING pragmas that allow for some limited ambiguity but it’s not pretty.
We can combine the closed type families with type classes to implement a generic fall-through. We add a new class
Overlap that takes one of our three possible colours:
class Overlap a where colour :: String
And we can now greet for any type without any overlapping instances:
λ hello @Int
Type classes are the easiest way to map from types to values so I think having “closed type classes” would make a great addition to GHC though I appreciate it’s a non-trivial undertaking, and currently beyond my skills. Edward Yang pointed me to a paper on instance chains which is pretty close to what I had in mind.