Type inference for Haskell, part 16

Posted on January 16, 2019

This is part 16 of the series on type inference for Haskell.

You might expect that the code from the previous sections of this series will need a massive overhaul and get much more complicated in order to support type classes. The good news is that the changes to the existing code is actually rather minor. Interestingly, type classes aren’t even considered in some of the core parts of the algorithm like unification. The bad news is that there is a lot of new code to add. Much of this new code will deal with issues you would never have thought of.

In this post, I’ll just look at the data. Some of the existing structures need to be modified a little, and several new structures need to be added.

(THIH Section 7.1, Basic Definitions)

I mentioned predicates like (Show a) in the previous post. There needs to be some data structure to store these. The structure is called Pred (show for predicate).

Here, the Id value (Id is a type alias for String) is the name of the class. The predicate (Show a) would be represented as:

IsIn "Show" (TVar (Tyvar "a" Star))

There also needs to be some way to combine predicates like (Show a) with a type like [a] -> String. A type with some predicates is called a “qualified type.” And so, the data structure is called Qual:

Note that this qualifies some undefined type t, not just a Type (though it is mostly used to qualify types). In addition to qualifying types, this is also used to qualify predicates. In fact, that is how instances of classes are defined:

(To avoid confusion, note that this is a different thing from an Impl, which was an implicitly typed binding.)

Qualifying a predicate with more predicates seems like an odd concept, but it lines up neatly with the syntax of an instance declaration.

To pull a code example from the paper itself (how meta!):

The predicate on the right, Types [a] is being qualified with the predicate on the left, Types a. It is worth noting that Inst only captures the type information about an instance. It doesn’t have the actual implementation. I guess that THIH assumes that the instance methods will be handled like normal explicitly-typed bindings.

Now, finally, we can define a class. This includes a list of the names of any superclasses and a list of all of the instances of this class.

The paper assumes that some code has already gathered up the list of all class definitions before type inference starts. This is familiar theme. There seems to be a lot of work to be done after parsing but before type inference starts.

(THIH Section 7.2, Class Environments)

It’s handy to have some structure to store the set of all of the classes that exist. This is all captured in a ClassEnv structure:

Personally, I would have used a Data.Map to store the mapping from Id (the name of a class) to the definition.

The ClassEnv structure gets passed through most of the inference functions so that they have access to this data when they want it. You might notice that it also includes a list of types called “defaults.” We’ll get to what that is good for in a future post.

The paper defines many functions for building up a class environment which aren’t terribly interesting so I won’t repeat them here. It’s probably worth taking a look at Section 7.2 to get a better sense of what the data stored for classes looks like.

(THIH Section 8, Type Schemes)

To top it all off, the types of variables now also need to have predicates. This is done by adding a Qual to the type inside a Scheme. The definition is now:

This now allows storing a type like (Show a) => [a] -> a for a variable.

Now that we are armed with knowledge of how classes and predicates are represented, the next several posts will focus on features of how type classes work. At the end, we’ll attach it back to the original inference code.