Functor hierarchy proposal and class system extension proposal

[Chung-chieh Shan]

Conor McBride <conor at strictlypositive.org> wrote in article <444CCA2D-3472-4A59-8A9F-548FADE84AF0 at strictlypositive.org> in gmane.comp.lang.haskell.prime:
> My plan also has the advantage of cheaper backward compatibility
> (for this and other (future) class splittings).

I find compatibility with future class splittings to be a compelling
feature to strive for, even *without* any default member definitions.
Inserting a new class in a hierarchy (as the Numeric Prelude proposes)
shouldn't cause any existing instances to break.  For example, say we
split

    class Num a where -- (+), (-), negate, (*), abs, signum

(I'll ignore fromInteger and the superclasses Eq and Show in this
message) into

    class Additive a where -- (+), (-), negate
    class (Additive a) => Num a where -- (*), abs, signum

In today's Haskell, all existing instances of Num will break.  The
problem is that the header "instance Num X where" used to mean "below
are definitions for (+), (-), negate, (*), abs, signum" but now means
"below are definitions for (*), abs, signum".

Here's a crazy idea to future-proof against such a split: let's make
every instance header declare not only the instance being defined but
also the superclass instance(s) being presupposed.  We will write

    instance () -> Num X where ...

to mean "below are definitions for (+), (-), negate, (*), abs, signum",
both before and after the split.  To say "below are definitions for (*),
abs, signum" (which only makes sense after the split), we will write

    instance (Additive X) -> Num X where ...

(I just made up the -> notation, and I'm not satisfied with it, though
it's definitely not the same as "instance (Additive X) => Num X where",
which needs UndecidableInstances.  Maybe "class (Additive a) => Num a"
should become "class (Additive a) -> Num a".)

Suppose that at t=3 we insert another class into the hierarchy:

    class Additive a where -- (+), (-), negate
    class (Additive a) => Ring a where -- (*)
    class (Ring a) => Num a where -- abs, signum

Now "instance (Additive X) -> Num X" still means "below are definitions
for (*), abs, signum".  To define just (*), we will write "instance
(Additive X) -> Ring X".  To define just abs and signum, we will write
"instance (Ring X) -> Num X".  We can also write "instance () -> Ring X"
to define (+), (-), negate, (*).

So each instance definition in the new syntax can explode into a whole
bunch of instance definitions in the old syntax.  I have high hopes that
this would work well with type-class synonyms.  For example, at t=4,
let's insert Monoid and Semiring into our class hierarchy:

    class Monoid a where -- (+)
    class (Monoid a) => Additive a where -- (-), negate
    class (Monoid a) => Semiring a where -- (*)
    class alias Ring a = (Monoid a, Semiring a)
    class (Ring a) => Num a where -- abs, signum

Still "instance (Additive X) -> Num X" means to define (*), abs, signum.
Still "instance (Additive X) -> Ring X" means to define just (*).
In fact even "instance () -> (Eq X, Show Y)" could be allowed.

If the same superclass appears multiple times then member names will
clash:

    class Su a where ...
    class (Su a, Su b) => Cl a b where ...

    instance (Su a) -> Cl a b where -- provide (Su b) and Cl a b
    instance (Su b) -> Cl a b where -- provide (Su a) and Cl a b
    instance (Su a, Su b) -> Cl a b where -- provide just Cl a b

    instance () -> Cl a b where
        -- not a backward compatibility concern because we couldn't have
        -- gotten our current Cl by splitting out both copies of Su, so
        -- we don't have to allow this instance at all

All this can be emulated using class aliases as proposed at
http://repetae.net/recent/out/classalias.html : as the EqOrd example
there shows, instead of the code at t=3 above, one would write

    class Additive a where -- (+), (-), negate
    class (Additive a) => Additive_Ring a where -- (*)
    class (Additive_Ring a) => Ring_Num a where -- abs, signum

    class alias Ring a = (Additive a, Additive_Ring a)
    class alias Num a = (Additive a, Additive_Ring a, Ring_Num a)
    class alias Additive_Num a = Additive a => (Additive_Ring a, Ring_Num a)

then write "instance Additive_Num X" instead of "instance (Additive X)
-> Num X".  But this requires a quadratic number of class aliases.
Besides, I like to understand *every* instance as covering not a single
edge in the hierarchy but a subgraph.

So far I haven't said anything about default member definitions.
What I want to suggest is, what if

    instance (Functor Blah) -> Applicative Blah where

means to hide the default instance for Functor Blah inside the
Applicative class, and

    instance () -> Applicative Blah where

means to use that default instance (which would still allow overriding
parts of it)?

I guess in terms of the class-alias proposal, my suggestion would be to
allow instances as part of a class alias!  I imagine a syntax like:

    class Functor a where ...
    class (Functor a) => Functor_Applicative a where ...

    class alias Applicative a = (Functor a, Functor_Applicative a) where
        fmap f x = pure f <*> x

-- 
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
<INSERT PARTISAN STATEMENT HERE>