Why were type classes difficult to implement?

Question

On slide 30/78 of this presentation, Simon suggests that implementation of type classes was a "despair" at the beginning. Is anybody aware why that was?

Answer 1

I guess I'm one of the few people who have first hand experience of why it was hard, since I implemented it in hbc when there was no prior art.

So what was clear from the Wadler&Blott paper was that type checking was an extension of Hindley-Milner type checking and that at runtime you should be passing dictionaries around. From that to an actual implementation is a rather big step. A good way to understand the difficulty is to actually implement it starting from just the Wadler-Blott paper.

First, you need to come up with the idea of a type checker that not only checks types but also transforms the program; inserting evidence (dictionaries) while type checking. You also need to figure out how to construct new dictionaries from old ones using the instance declarations as an inference system.

It might all seem obvious in retrospect, but remember that since that time a lot of papers with explanations have been written. Understanding how to do something from a paper is very different from coming up with it in the first place.

Furthermore, you want type classes to be reasonably efficient which leads to its own set of problems.