An Alternative History of Haskell: being lazy without class?

Question

[The q is a play on the title of this 2007 survey of Haskell.]

tl;dr I have a couple of connected questions about Haskell's overloading mechanisms. I'll ask first then explain why. I'm looking at the discussions when overloading was 'discovered' around 1988/1989, and imagining how would some of the alternative designs have worked out, if we knew then what we know now. (I'll maybe add more material/references if commenters ask.)

1. Is it essential for typeclasses to be able to bundle together more than one method? Or would it work to have each method in a separate class, with superclass constraints to link methods (as for example Eq is a superclass of Num)?

2. If we have one method per class, do we really need classes? Or could we just express overloading direct over the methods?

1. One method per class?

A frequent complaint about the Prelude class Num is that it bundles together all arithmetic operators. But mathematical purity says we should have an Additive class, a Multiplicative class, etc, etc, with Additive being a superclass of Multiplicative.

If we make an instance Num for some datatype, we must define an implementation for every operator whether or not it makes sense. (Or if you don't declare an implementation, the compiler gives you one anyway, that returns undefined at run time.) What we want for operators that don't make sense over that datatype is a rejection at compile time.

Aside from Mathematical purity, there's a particularly down to earth problem/source of much puzzlement on StackOverflow: Num includes method fromInteger. There's a hidden call to fromInteger built into every integer literal. (Which is to say that what looks like a literal in any other programming language is not a literal in Haskell.) Say your Num instance is for arithmetic over vectors or matrixes. If you put

x :: Vector
x = 10

Most newbies expect a compile fail: they forgot to wrap the literal in a constructor to turn it into a vector. Instead, it compiles and if you're lucky, fails at run time with undefined; or perhaps happily executes and gives puzzling results.

Changing the design of Num now is just too hard, so we live with it; but what if we could start afresh and separate concerns for the operators? Would we end up with each operator in a separate class?

And similar questions for the other Prelude classes with multiple methods. (Plenty of them have a single method anyway. But for example there's grumbling from people who want a Monad without return.)

2. Overload the methods; don't need no class

The very first design for overloading section 1 of Wadler's 1988 memo -- and I mean before the early 1989 paper with Blott -- doesn't mention class. It just wades right in and declares a bunch of operators as overloadable, with their type signature; then gives instances for them.

I read section 1 as setting up something of a straw man: at the end it points out some difficulties, which section 2 remedies (with class). But I see some mis-steps in section 1, so the difficulties can be avoided without introducing a new entity into the language IMHO. (This is no criticism of Wadler: it's amazing how much he anticipated so early on.)

The term class Wadler draws straight from OOP. But oh woe!

Haskell classes are not very like OOP classes: there's no class inheritance/subtyping; there's no encapsulation of data; there's no information hiding. (Haskell can do all those things, but the concerns are separated into other mechanisms.)

And the confusion it causes learners coming to Haskell from OOP languages is immense. Perhaps Haskell could use another term.

But rather: with only one method per class, just cut out the middle man. We still implement as dictionary-passing (after all, the dictionary gets passed to a version of the method, as an extra invisible argument); the class gets type-erased anyway; we can attach the evidence-passing to the method rather than the class(?)

In type inference, we express constraints (wanted or given) as "needs an overload for (+) at type Vector", etc. (I won't deflect into pondering syntax: it would need method names appearing in type signatures; which would probably have caused palpitations in 1988; but nowadays we're happy to put types in terms with explicit type application; so why not vice versa?)

Answer 1

I was thinking about lots of these things. I do consider typeclasses one of the less principled parts of Haskell, in that they don't derive directly from theoretical ideas, being more pragmatic.

One nitpick:

with superclass constraints to link methods (as for example Eq is a superclass of Num)?

If a typeclass is not a grouping of multiple methods, what is the point of subclassing? It seems a bit awkward to have typeclasses that contain multiple methods, but can only be implemented one at a time. Direct method overloading seems to make more sense.

As mentioned in the comments, typeclasses group methods together conveniently. Amongst other things, this prevents context blowup: you'd have to enumerate every method you use in the context.

I think you'd only gain, not lose in expressiveness by having overloading over methods.

My proposal for overloading in a future Haskell would be as follows:

Overloading idea

1. Individual methods declared as abstract and overloadable - type signature only, no implementation.

2. Constraints which group zero or more of the following:

   • Superclass constraints
   • (Already declared) methods
   • Laws over the methods - you can then enable automatic testing.

   (Combinations of) types would then be declared/asserted as implementing a constraint, to ensure their method instances are law-abiding.

Functions can then be constrained on Constraint or Has(method).

It would also be convenient to include implications - if a (combination of) types implements a constraint A, this is what implementation it will have for methods a...n. This would make it easier to define constraints such that 'If a type implements A, its B instance looks like this'. We have a few of these, even in base, and no convenient way of expressing them. However, I have no idea if these implications would be decidable.

This would allow unlawful types like Set to implement map but not Functor, and you choose which one to constrain on depending on whether you need (or want) the laws.

As a bonus, it will also make it easier to implement 'burning bridges' changes like Foldable Traversable and Applicative Monad while breaking less code.