Typeclasses vs Modules
31 points by abhin4v
31 points by abhin4v
One of the pervasive problems with type classes is that they lock you into one global meaning and implementation for a name.
If absolutely everyone agrees that this one meaning always makes sense, that’s fine, but if your understanding evolves, you’ve now got a major problem because any change can break unexpected parts of your ecosystem.
We ran into just this with the Hashable type class in Haskell many years ago. The standard implementation of Hashable for integers is to just convert to an Int, so basically the identity function.
For some uses, this is fine, but for a majority of hashing purposes, you want to mix the bits, and because fast hashing with good mixing properties has been an active area of research for many years, you can very reasonably expect a large program to have different hashing needs in different places, depending either on use case or the age of a section of code.
This is all pretty easy to achieve with an ML-style module system, but type classes are literally the wrong tool for this job due to their virality and rigidity. Unfortunately I didn’t come to this conclusion until way too late, and the Backpack module system in Haskell didn’t even exist at the time we were struggling with this.
The deeper problem with type classes is they make a policy choice look like an intrinsic property of a type.
An integer doesn’t have one natural hash. It has a representation, and you choose a hashing strategy for a particular consumer: bucket selection, fingerprints, composite keys, partitioning, and so on. Those consumers can need different properties. A global Hashable Int instance erases that distinction.
If I was redoing Hashable using Haskell’s Backpack module system, it would look quite different. However, Backpack is also kind of a pain in the ass to work with, whereas type classes also have this seductive property of being very easy and notationally lightweight.
Modules in Haskell are a plate of steamed broccoli, while type classes are a quart of ice cream. Ocaml has much nicer ergonomics for its module system, but they’re somewhat uglier to read than type classes.
Rust shows how this can be addressed using typeclasses. The hash method on the Hash trait requires a parameter that implements Hasher. This allows the hashing strategy to be customized as needed by the caller.
let hasher = &mut DefaultHasher::new();
1234.hash(hasher);
dbg!(hasher.finish());
That looks like a better decision on the surface, but I don't think it helps all that much. You still need to be able to compare keys for both hash equality and value equality, but the trait only allows hashing, so if you want to do case insensitive hashing over strings, for example, you end up with a newtype wrapper, just as you would in Haskell.
struct CaseInsensitive(String);
sensitive.get("Content-Type");
insensitive.get(&CaseInsensitive("content-type".into()));
It's somewhat worse than this in Rust, in practice, because of the borrow checker getting in the way of zero-copy comparisons.
OCaml would instead let you apply the table functor twice to two modules over the same string type, and you'd be done.
That hashing has no bearing on equality is natural. Applications such as hash maps bound on both Hash and Eq.
Using a newtype for this pattern is unnecessary as the hasher itself can implement case insensitivity on strings. Even if it couldn't there would be no problem with using a newtype.
The existence of the borrow checker poses no obstacle to zero-copy comparisons. In any case Unicode prevents in-place case conversion.
That’s one of the things I liked about Scala: with implicits (and now with givens/better syntax surrounding typeclasses) you can choose what instance of a typeclass you want to pass to any given function.
Though IIRC, this lack of “typeclass coherence” is considered a downside by many haskellers. I don’t think a module system gets around the cons associated with this approach, but maybe it does because it can be coarser grained than passing different implicits?
To illustrate the point about bundling operations with algebraic laws, you could show a similar example in a language where the laws can be encoded directly as fields with a dependent type, e.g. https://leanprover-community.github.io/mathlib4_docs/Mathlib/Algebra/Group/Semigroup.html#AddSemigroup.