Functor hierarchy proposal and class system extension proposal

[Conor McBride]

Hi

On 2 Jan 2011, at 09:29, Malcolm Wallace wrote:

> See also
>    http://repetae.net/recent/out/classalias.html
>    http://www.haskell.org//pipermail/libraries/2005-March/003494.html
>    http://www.haskell.org//pipermail/haskell-prime/2006-April/001344.html
>    http://www.haskell.org//pipermail/haskell-prime/2006-August/001582.html

A proposal from Jón Fairbairn for how to add default superclass method
definitions gained some traction, and deserves to be revi(v/s)ed now, I
think.

Some superclass relationships are `shallow' interface extensions:  
MonadPlus
does not give you a standard way to implement Monad, just more  
functionality
within a monad. Other superclass relationships `deepen' existing
functionality---if you have Ord, you can certainly make Eq; if you have
Monad, you can certainly make Applicative, etc. The former is currently
well supported, the latter badly.

Jón's proposal was to improve the latter situation by allowing the  
subclass
to specify a default (partial) implementation of a superclass. So we  
might
write

   class Applicative f where
     return :: x -> f x
     (<*>) :: f (s -> t) -> f s -> f t
     instance Functor f where
       fmap = pure . (<*>)

giving not only a subclass constraint (Functor f =>) but also a standard
means to satisfy it. Whenever an Applicative instance is declared, its
Functor sub-instance is unpacked: buy one, get one free.

This, on its own, is not quite enough. For one thing, we need a way to
switch it off. I should certainly be permitted to write something like

   instance Applicative Blah where
     return = ...
     (<*>) = ...
     hiding instance Functor Blah

to prevent the automatic generation of the superclass instance. The
subclass constraint would still apply, so in order to use the  
Applciative
functionality of Blah, it would have to be a Functor otherwise, e.g., by
being Traversable. This `hiding' option was missing from Jón's proposal,
but it seems crucial to address the potential for conflicts which was
identified in the discussion at the time.

It's also clear that we must be able to override the default behaviour.
When the class declaration has a superclass instance, but not otherwise,
a subclass instance should be entitled to override and extend the  
methods
of the superclass instance thus generated. It seems unambiguous to allow
this to happen without repeating the "instance Mutter Something". So
we'd have


   class Monad f where
     (>>=) :: f s -> (s -> f t) -> f t
     instance Applicative f where
       ff <*> fs = ff >>= \ f -> fs >>= \ s -> return (f s)

and we'd still be able to write

   instance Monad Maybe where
     return = Just              -- completing the generated Applicative
     Just s  >>= f = f s
     Nothing >>= _ = Nothing

and acquire Monad, Applicative, Functor.

No new instance inference semantics is required. In order to transform
code under this proposal to code acceptable now, one need only keep
track of which methods belong to which class and which classes have
default superclass instances: each compound instance can then be
split into its individual components before compilation under the
current rules.

Is this clear? Does it seem plausible?

All the best

Conor