3
$\begingroup$

[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?)

$\endgroup$
3
  • 1
    $\begingroup$ From an engineering perspective, classes bundling methods together is nice for at least three reasons: it gives a central place to attach laws that relate methods (at the very least as documentation), default implementations are handy, and it can abbreviate signatures in a way that's nice for humans (e.g. compare ((+) a, (*) a, fromInteger a, div a) => a -> a to Num a => a -> a). Of course none of these considerations is fundamental -- they don't affect the expressive power of the language at all -- but they are convenient nonetheless. $\endgroup$ Feb 15, 2019 at 15:39
  • $\begingroup$ Thanks: anything that's divisive will have multiplicative and additive as superclasses, so we don't need those explicitly. And nothing to stop us creating a dummy method num with superclasses, um supermethods, all of the above. Attach the laws to num if you like. Default implementations are of methods so yes we need a way to declare them, but not a class. IMO $\endgroup$
    – AntC
    Feb 15, 2019 at 21:25
  • $\begingroup$ "Perhaps Haskell could use another term [for class]." for lots and lots and lots more things, too. :) $\endgroup$
    – Will Ness
    Dec 29, 2019 at 8:47

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ " It seems a bit awkward to have typeclasses that contain multiple methods, ..." To be clear: my musing is to do away with typeclasses altogether. The mechanism for grouping would be to have a method with multiple super-methods/constraints. (For example divide has constraint multiply, add, greater, equal, ...) And there'd be the current simplification that you need mention only one, and get all its super-methods for free. $\endgroup$
    – AntC
    Aug 10, 2021 at 3:16
  • $\begingroup$ "'If a type implements A, its B instance looks like this'" Yeah lots of newbies want that. Can't be done in Haskell. You could look at language Habit (M.P.Jones and Morris.) "Laws over the methods" hmm how would you express or verify those? You could look at Liquid Haskell. $\endgroup$
    – AntC
    Aug 10, 2021 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.