Tuples, aside from their weird syntax, are just like any other data type.
You can even partially apply a tuple type constructor by writing it in
“prefix” style. For instance,
(Int, Bool) and
(,) Int Bool are two ways
of writing the same type. This flexibility allows tuples to be manipulated
in all the ways we’re used to in Haskell.
Unfortunately, constraint tuples do not enjoy the same privileges as their relatives, the tuple data types. In particular, it is not possible to partially apply a constraint tuple type constructor in the conventional sense, which can make them somewhat awkward to use at times. In this post, I will discuss four different techniques for working around this limitation of constraint tuples.
A trove of tuples
Tuples in Haskell can have several different meanings depending on the context.
For instance, the tuple in
(a, b) can be a data type, a data constructor, or
a constraint depending on where it is used. Here is a piece of code that
demonstrates each of these three meanings:
As far as syntactic puns goes, tuples are one of GHC’s longest-running gags. One drawback of punning tuple syntax is that there can be ambiguous situations where it is unclear precisely which form of tuple is being used. As a concrete example, imagine this code:
MyTuple a type synonym for a tuple data type or a constraint tuple? The answer
depends on whether the kinds of
In the absence of additional kind information, GHC will conservatively assume that
MyTuple refers to a data type, not a constraint. If this was not the
programmer’s intention, they can clarify their intentions by adding extra
kind annotations, like so:
In this sense, GHC has a very limited form of type-directed name resolution. This trick is usually sufficient to distinguish constraint tuples from tuple data types in most situations.
Tuples and partial application
Just as tuples have special syntax for fully saturated applications, tuples also have special syntax for partial applications. For instance, here is some code from earlier in this post, but rewritten to use this partial application syntax:
To complete the analogy, we should also define
ReadAndShow using a partially
applied constraint tuple. Intuitively, you might expect that this would get the
Surprisingly, this won’t work. If you feed this code into GHC, it will regurgitate:
This error message would suggest that GHC thinks the
(,) (Read a) (Show a)
refers to the type constructor for a data type, not a constraint. What’s more,
even if you add extra kind information:
GHC still refuses to recognize
(,) as being the name of a constraint tuple.
The unfortunate reality is that GHC’s type-directed name resolution trick for
tuples only applies to fully applied tuples. Any use of a partially applied tuple
will be interpreted to mean a tuple data type. In other words, partially applying
a constraint tuple is essentially prohibited. Bummer.
Regaining partial application
GHC may prohibit us from partially applying constraint tuples in a straightforward
fashion, but that’s clearly not the end of the story. Otherwise, I wouldn’t be
writing this blog post! We needn’t get discouraged by the inability to use
in constraints because there are other ways to accomplish the same thing. All we
need is some creativity and a couple of language extensions. (OK, perhaps slightly
more than a couple.)
Solution 1: Roll your own constraint tuples
If we can’t use GHC’s built-in constraint tuples, a feasible alternative is to just bake our own from scratch. But what exactly are constraint tuples, anyway? Let’s try to reverse engineer them.
To pick one particular example, the constraint tuple used in
(Read a, Show a) takes two
Constraints as inputs (
Read a and
and produces another
Constraint as an output. We only have one tool in our
toolbelt for crafting new types that live
Constraint: type classes.
As luck would have it, type classes provide exactly what we need to assemble
a makeshift constraint tuple. Here is a decent first attempt:
CTuple2 has two
Constraint-kinded arguments that also function as the
superclasses. This is possible thanks to the power of GHC’s
ConstraintKinds extension, as well as supporting roles from
UndecidableSuperClasses (which we need in order to define a class with a
superclass that is a bare type variable). Now, we should be able to take
(Read a, Show a) and replace it with
CTuple2 (Read a) (Show a).
For example, we can do this:
And it compiles! (Well, after enabling
FlexibleContexts, that is.)
CTuple2 is still only half-baked. If you try to actually
roundtrip somewhere, you’re likely to run into trouble.
Here is one such troublemaker:
If you compile this, GHC will whine thusly:
GHC is pouting because it wants there to be an instance of
scope in order to satisfy the
CTuple2 constraint in
(Whereas we assumed the existence of such an instance in the definition
roundtrip itself, so we did not need it there.) We could try
to shut GHC up by just defining a one-off instance like so:
This works, but it’s not a terribly robust solution. If you need to use any
other pair of constraints, such as
CTuple2 (Eq a) (Ord a), then you’ll also
need to define a corresponding
CTuple2 (Eq a) (Ord a) instance. Since there
are infinitely many such combinations of constraints, we would have to write
a lot of code to achieve parity with built-in constraint tuples this way.
Thankfully, we can get away with only writing one instance instead of
infinitely many. With the help of
FlexibleInstances, we can implement the
one instance to rule them all:
This will make
roundtripInt compile, as well as any other conceivable use
CTuple2. Normally, defining “catch-all” instances like the one above
is considered bad practice, since any other instance that a user might want
to define will overlap with it . In the particular case of
however, having a catch-all instance is just fine, as this is really the only
CTuple2 you’ll ever need. This is a rare scenario where we will
choose to embrace catch-all instances rather than shun them.
To recap, we were able to roll our own constraint tuple like so:
The crucial bit here is that since
CTuple2 is a class, it can be partially
applied. On the other hand, if we were to define
CTuple2 as a type synonym:
The same property would not hold true, since type synonyms cannot be partially
applied like classes can . For this reason, the class-and-instance
CTuple2 can be used in strictly more places than the type
synonym version can.
This trick—defining a class accompanied by a single catch-all instance—is called the “constraint synonym” encoding . It is worth noting that I am far from the first person to make use of this encoding. This blog post by Icelandjack has a much more thorough exposition on constraint synonyms and all of the interesting things one can do with them.
Solution 2: Roll your own constraint newtypes
Another common name for constraint synonyms is “constraint newtypes”. The rationale behind this analogy is that newtypes provide a cheap way to define something that is like another type, but with a new name. For instance, in the following constraint synonym:
MyC is basically the exact same type as
C, but with a distinct name.
It’s almost as if you wrote
newtype MyC = MyC C!
In GHC, the analogy goes even deeper than that. When the class declaration for
MyC is compiled to Core, it becomes a dictionary data type with a single
field of type
C to represent its superclass. As an optimization, GHC takes
all dictionary data types with exactly one field and turns them into newtypes.
In other words,
MyC is quite literally a newtype at the Core level .
However, not all constraint synonyms become newtypes in Core. One
counterexample is the
CTuple2 class. Recall its definition:
CTuple2 may look like a class newtype on top of a built-in constraint tuple
of size 2, but it’s not. The reason is that the
(a, b) to the left of
=> is not, strictly speaking, a constraint tuple. It’s simply syntax
denoting the combination of two superclasses,
(Yet another way tuples are punned in Haskell!)
To put in another way, this is the dictionary version of
CTuple2 in Core:
Rather than a newtype on top of
CTuple2 is a data type with two
separate fields of types
In practice, this difference probably won’t matter, since
CTuple2 a b looks and behaves like
(a, b) would anyway. But it does raise
the question: can we define
CTuple2 another way so that it is a newtype
on top of
(a, b) in Core?
As it turns out, we can. The idea is that instead of giving
two superclasses, we only give it one. To accomplish this, we make use of
good-old-fashioned type synonyms. First, we define a type synonym for
When used on the right-hand side of a type synonym like this,
(a, b) really
does refer to a built-in constraint tuple type. With
hand, defining a “newtype” version of
CTuple2 is as easy as this:
CTuple2 will compile to (roughly)
newtype CTuple2 a b = CTuple2 (MyTuple a b) in Core.
Alternatively, if you want to minimize the number of types you have to define, you
MyTuple into the definition of
CTuple2 like so:
Yes, you read that right: when used to the left of
(a, b) and
((a, b) :: Constraint) compile to different things in Core. Is this confusing?
Probably. Don’t blame me, I didn’t design the compiler.
(At least, not this part.)
Solution 3: Decompose constraint tuple applications with type families
The previous two solutions get the job done, but in some sense, they’re cheating a bit. That is because they give you ways to partially apply things like look like GHC’s built-in constraint tuples, but they’re still technically different types altogether. What if we want to use actual, honest-to-goodness constraint tuples types instead? At this point, we have to get even more creative.
While we can’t partially apply a constraint tuple type constructor directly
in source Haskell (as in
(,) (Read a) (Show a)), these type constructors
are still very much real in the eyes of GHC. We will crucially rely on this
fact in order to get our hands on them. In particular, GHC lets you decompose
applications of type constructors by way of type families. For instance,
if you are given the type
f x, you can decompose it into
f like so:
We can test out
DecomposeType in GHCi by using the
:kind! command, which
both computes a type’s kind and reduces type families that appear in the
type itself as much as possible:
This is, admittedly, a silly use case for this feature, as we could have
Maybe directly instead of the more convoluted
DecomposeType (Maybe Int). On the other hand, we can define a variant
DecomposeType that is much more useful:
This time, we’re only dealing with
Constraint-kinded type constructors that
take two arguments. This is because
DecomposeConstraint is tailor-made to
decompose the constraint tuple in a type like
(Read a, Show a). As proof
that this works, behold:
Ta-da! This constraint tuple type constructor looks a little funny since it’s
usually not exposed to the programmer like that, but that’s exactly what we
were looking for. On the other hand, typing out
time we want to use this type constructor is a little cumbersome, so we
can make our lives a little easier by defining a shorthand for it:
This version of
CTuple2 behaves just like its cousins in the previous two
sections, but it evaluates directly to GHC’s built-in constraint tuple
constructor instead of making use of an auxiliary type class.
Solution 4: Decompose constraint tuple applications with type synonyms
There is one drawback to the approach in the
previous section: you cannot define type class instances that mention
in the instance head. For instance, if you tried this compiling this
GHC will pump the brakes immediately:
Blast. If we want to work around this limitation of GHC’s, we’ll need to reach even deeper into our magic hat. Luckily, we still have one more trick in our repertoire. The idea is the same: decompose an application of a type constructor of the right kind. This time, however, we’re going to avoid using type families altogether and rely on type synonyms to do the actual decomposition part.
It might sound a bit strange to use a type synonym to decompose a type constructor application. Trying to decompose things the “simple” way just won’t cut it. This code:
Won’t even get past the parser. Type synonym declarations require all of the arguments to be bare type variables, so this idea seems doomed to fail. But we shouldn’t give up yet. Even though the arguments of a type synonym must be bare variables, there are no such restrictions on what their kinds can be. That’s right: it’s time to get fancy.
Enlisting the help of the
PolyKinds extensions, we can
define a type synonym that decomposes an application of a type constructor
at the kind level. First, we need a data type to store this kind :
Now we need a way to decompose something of kind
This is the fancy part. We take the argument (which must have kind
P (f a b)),
f part and return it as the right-hand side type. The use of
both a kind variable and a type variable is only possible on GHC 8.0 or later,
where types and kinds are one and the same.
CTuple2 is just a matter of plumbing the right types through:
This version of
CTuple2 can do all the things that the version in the previous
section can do with the added benefit of being usable in instance heads.
I have demonstrated four different techniques for defining partially applicable
constraint tuples types in GHC. Which technique you prefer the most will likely
depend on your personal tastes, but they all accomplish mostly the same things.
I have used
CTuple2 as the running example
throughout this post, but the same ideas also allow you define
CTuple4, or whatever-sized constraint tuple you may desire. As a proof-of-concept,
I have created a
library which defines constraint tuples of varying sizes using each of the
four techniques documented here.
The term “constraint synonym” should not be confused with a type synonym that uses a constraint on the right-hand side, such as
type MyShow a = Show a. ↩
To be pedantic, newtypes don’t actually exist in Core, since all uses of newtypes are compiled to coercions. For the sake of this post, however, this distinction isn’t important. ↩