Replacing type classes with records affects optimisation

Posted on March 20, 2018

It is somewhat common to suggest using records instead of type classes for particular domains for which type classes are not deemed idiomatic. However, this suggestion should be taken with caution as the change will have consequences on how your program is optimised. Using records instead of type classes can lead to much slower programs.

In order to provide an interface for propositional logic, we might provide a type class which allows the constructors to be overloaded. We can then provide a direct interpretation of Prop which evaluates an expression to a truth value.

However, one might be tempted to avoid using a type class and instead perform the manual type class desugaring in order to be able to more easily modify and extend an interpretation.

We can then use both versions in order to implement a helper function which turns a list into a chain of disjunctions.

We can then instantiate each function by either supplying a type argument or the dictionary directly in the latter case.

What’s the difference between these two versions? The process of optimisation is different. In the first case, the overloading of ors will be eliminated by specialisation. In the later case, the static argument will be eliminated by SpecConstr. When we define these definitions in the same module as our earlier definitions of ors and dors then both definitions result in essentially the same code as each other. The overhead is eliminated.

However, when we use ors or dors in another module, they behave quite differently. If we mark ors as INLINABLE then it will also be specialised in other modules. However, SpecConstr does not work across module boundaries. As a result, dors will not be specialised on the static argument and the dictionary overhead will remain.