# Class system extension proposal

### From HaskellWiki

(Added links to research on extensible superclasses) |
m (→Motivation: code format) |
||

(7 intermediate revisions by 3 users not shown) | |||

Line 5: | Line 5: | ||

The current class system in Haskell is based on the idea that you can often provide default implementations for class methods at the same time as defining the class, by using other methods of the class or its ancestors. However consider the following hierarchy, adapted from [[Functor hierarchy proposal]] and [[The Other Prelude]]: |
The current class system in Haskell is based on the idea that you can often provide default implementations for class methods at the same time as defining the class, by using other methods of the class or its ancestors. However consider the following hierarchy, adapted from [[Functor hierarchy proposal]] and [[The Other Prelude]]: |
||

<haskell> |
<haskell> |
||

− | class Functor m where |
+ | class Functor m where |

− | fmap :: (a -> b) -> m a -> m b |
+ | fmap :: (a -> b) -> m a -> m b |

− | class Functor m => Applicative m where |
+ | class Functor m => Applicative m where |

− | return :: a -> m a |
+ | return :: a -> m a |

− | apply :: m (a -> b) -> m a -> m b |
+ | apply :: m (a -> b) -> m a -> m b |

− | (>>) :: m a -> m b -> m b |
+ | (>>) :: m a -> m b -> m b |

− | ma >> mb = (fmap (const id) ma) `apply` mb |
+ | ma >> mb = (fmap (const id) ma) `apply` mb |

− | class Applicative m => Monad m where |
+ | class Applicative m => Monad m where |

− | (>>=) :: m a -> (a -> m b) -> m b |
+ | (>>=) :: m a -> (a -> m b) -> m b |

</haskell> |
</haskell> |
||

For all concrete instances of <hask>Monad</hask> we can define <hask>fmap</hask>, <hask>apply</hask>, and <hask>(>>)</hask> in terms of <hask>return</hask> and <hask>(>>=)</hask> as follows: |
For all concrete instances of <hask>Monad</hask> we can define <hask>fmap</hask>, <hask>apply</hask>, and <hask>(>>)</hask> in terms of <hask>return</hask> and <hask>(>>=)</hask> as follows: |
||

<haskell> |
<haskell> |
||

− | fmap f ma = ma >>= (\a -> return (f a)) |
+ | fmap f ma = ma >>= (\a -> return (f a)) |

− | apply mf ma = mf >>= \f -> ma >>= \a -> return (f a) |
+ | apply mf ma = mf >>= \f -> ma >>= \a -> return (f a) |

− | ma >> mb = ma >>= \_ -> mb |
+ | ma >> mb = ma >>= \_ -> mb</haskell> |

− | </haskell> |
||

In other words, we'd like to be able to write: |
In other words, we'd like to be able to write: |
||

<haskell> |
<haskell> |
||

− | class Applicative m => Monad m where |
+ | class Applicative m => Monad m where |

− | (>>=) :: m a -> (a -> m b) -> m b |
+ | (>>=) :: m a -> (a -> m b) -> m b |

− | fmap f ma = ma >>= (\a -> return (f a)) |
+ | fmap f ma = ma >>= (\a -> return (f a)) |

− | apply mf ma = mf >>= \f -> ma >>= \a -> return (f a) |
+ | apply mf ma = mf >>= \f -> ma >>= \a -> return (f a) |

− | ma >> mb = ma >>= \_ -> mb |
+ | ma >> mb = ma >>= \_ -> mb |

</haskell> |
</haskell> |
||

and be able to define new instances of <hask>Monad</hask> just by supplying definitions for <hask>return</hask> and <hask>(>>=)</hask> by writing: |
and be able to define new instances of <hask>Monad</hask> just by supplying definitions for <hask>return</hask> and <hask>(>>=)</hask> by writing: |
||

<haskell> |
<haskell> |
||

− | instance Monad T where |
+ | instance Monad T where |

− | ma >>= a_mb = ... -- some definition |
+ | ma >>= a_mb = ... -- some definition |

− | return a = ... -- some definition |
+ | return a = ... -- some definition |

</haskell> |
</haskell> |
||

Line 62: | Line 62: | ||

===Implications=== |
===Implications=== |
||

− | The most important implication of this proposal would be that the resolution of an overloaded method would depend on the instances in scope in the module where the method is called. Therefore overloading would need to be resolved before modules are conceptually merged together (especially important when considering whole program optimization), and in particular overloading of the body of an inlined function would need to be resolved using the module where the function was defined not the module where it is inlined. |
+ | One implication of this proposal would be that the resolution of an overloaded method would depend on the instances in scope in the module where the method is called. Therefore overloading would need to be resolved before modules are conceptually merged together (especially important when considering whole program optimization), and in particular overloading of the body of an inlined function would need to be resolved using the module where the function was defined not the module where it is inlined. |

+ | |||

+ | Another implication is that the current class system where each level in the hierarchy is independent from other levels (via separate instance declarations), solves the problem of "multiple inheritance": given <code>(Functor m, Applicative m, Monad m)</code> the compiler can find the definition for <code>fmap</code> just by looking at the instance for <code>Functor m</code> alone, whereas with the proposal the compiler would have to consider all the predicates in the context to determine the source of each overloaded function. This may or may not be a problem. |
||

==Explicit import/export of instances== |
==Explicit import/export of instances== |
||

Line 74: | Line 74: | ||

) where |
) where |
||

− | import Foo (instance M (F a) hiding M (F String)) |
+ | import Foo (instance Monad a hiding Monad Maybe) |

data T a |
data T a |
||

data F a b |
data F a b |
||

</haskell> |
</haskell> |
||

− | where the context is elided because this isn't used in instance selection (at the moment). |
+ | where the context is elided because this isn't used in instance selection (at the moment). The import directive tells the compiler to use all <hask>Monad</hask> instances exported by <hask>Foo</hask> except for the <hask>Monad Maybe</hask> instance (it doesn't matter whether or not <hask>Foo</hask> actually does export a <hask>Monad Maybe</hask> instance - all that matters here is that we don't want it if there is one). |

==Typeclass synonyms== |
==Typeclass synonyms== |
||

Line 86: | Line 86: | ||

See http://repetae.net/john/recent/out/classalias.html. |
See http://repetae.net/john/recent/out/classalias.html. |
||

+ | |||

+ | === Superclass defaults === |
||

+ | |||

+ | The above propsal handles two separate issues, contexts with lots of class names, and defaults. The compatible [[superclass defaults]] propsal separates these two issues. |
||

==Extensible superclasses== |
==Extensible superclasses== |
||

Line 91: | Line 95: | ||

This increases modularity by allowing us to add a new superclass to a class without modifying the class itself, just as at present we can always add new subclasses. |
This increases modularity by allowing us to add a new superclass to a class without modifying the class itself, just as at present we can always add new subclasses. |
||

− | See http://taichi.ddns.comp.nus.edu.sg/taichiwiki/GPHomePage for an example of how this extension solves an important problem in generic programming. |
+ | See http://taichi.ddns.comp.nus.edu.sg/taichiwiki/GPHomePage for a motivating example. |

+ | |||

+ | More details can be found in the paper ''Modular Generic Programming with Extensible Superclasses'', available in ps format from |
||

+ | http://www.comp.nus.edu.sg/~sulzmann/publications/wgp06-modulargeneric.ps or in pdf from http://users.ox.ac.uk/~wolf2335/publications/generic.pdf. |
||

− | More details can be found in the paper ''Modular Generic Programming with Extensible Superclasses'', available in ps format from http://www.comp.nus.edu.sg/~sulzmann or in pdf from http://web.comlab.ox.ac.uk/oucl/work/meng.wang/ |
+ | ==Quantified contexts== |

− | (click on home page link then publications link) |
+ | A minor annoyance is that the <hask>Monoid</hask>, <hask>MonadPlus</hask> and <hask>ArrowPlus</hask> are all essentially the same. Allowing forall in contexts gives a way to combine these classes back into one. See [[Quantified contexts|the proposal]] for details. |

## Latest revision as of 18:27, 2 March 2012

## Contents |

## [edit] 1 Allowing superclass methods to be overridden in derived classes

### [edit] 1.1 Motivation

The current class system in Haskell is based on the idea that you can often provide default implementations for class methods at the same time as defining the class, by using other methods of the class or its ancestors. However consider the following hierarchy, adapted from Functor hierarchy proposal and The Other Prelude:

class Functor m where fmap :: (a -> b) -> m a -> m b class Functor m => Applicative m where return :: a -> m a apply :: m (a -> b) -> m a -> m b (>>) :: m a -> m b -> m b ma >> mb = (fmap (const id) ma) `apply` mb class Applicative m => Monad m where (>>=) :: m a -> (a -> m b) -> m b

fmap f ma = ma >>= (\a -> return (f a)) apply mf ma = mf >>= \f -> ma >>= \a -> return (f a) ma >> mb = ma >>= \_ -> mb

In other words, we'd like to be able to write:

class Applicative m => Monad m where (>>=) :: m a -> (a -> m b) -> m b fmap f ma = ma >>= (\a -> return (f a)) apply mf ma = mf >>= \f -> ma >>= \a -> return (f a) ma >> mb = ma >>= \_ -> mb

instance Monad T where ma >>= a_mb = ... -- some definition return a = ... -- some definition

- The idea of making a subclass ofMonadwas only discovered after many people had already usedApplicativein their programs. Therefore many existing programs already contain instance declarations forMonadas outlined above, so we would prefer not to have to change them just because the hierarchy has been refined to add extra functionality these existing programs don't use. This also applies to other hierachies in wide use at the moment, where changes have been proposed eg theMonadhierarchy.Num
- The implementation of in terms of(>>)for(>>=)is much simpler than the default implementation provided byMonad.Applicative
- The example shows that sometimes the default implementation of a method depends on which subclass we are using, and so acts as a counterexample to the current assumption that default implementations can be provided in the class where the method is introduced.

### [edit] 1.2 Concrete proposal

- Class and instance declarations would allow method implementations to be given for any methods in the class or any ancestor class.
- Whenever an instance declaration is visible there would always be a full set of instance declarations for all ancestor classes, by supplementing the set of explicitly given instance declarations that are visible in a module by automatically generated implicit instance declarations.
- The most specific method implementation would always be chosen (ie prefer an explicit instance method over a class method and prefer a subclass method to a superclass method)
- Modules would only export explicit instance declarations

### [edit] 1.3 Clarifications

- Separate compilation is still possible because all that's happening in the proposal is that the set of explicit instance declarations in scope in the module would be supplemented by a set of compiler-generated implicit instance declarations which are only visible in the module being compiled.

### [edit] 1.4 Implications

One implication of this proposal would be that the resolution of an overloaded method would depend on the instances in scope in the module where the method is called. Therefore overloading would need to be resolved before modules are conceptually merged together (especially important when considering whole program optimization), and in particular overloading of the body of an inlined function would need to be resolved using the module where the function was defined not the module where it is inlined.

Another implication is that the current class system where each level in the hierarchy is independent from other levels (via separate instance declarations), solves the problem of "multiple inheritance": given `(Functor m, Applicative m, Monad m)`

the compiler can find the definition for `fmap`

just by looking at the instance for `Functor m`

alone, whereas with the proposal the compiler would have to consider all the predicates in the context to determine the source of each overloaded function. This may or may not be a problem.

## [edit] 2 Explicit import/export of instances

This is needed so that large programs can be built without fear of colliding instance declarations between different packages. A possible syntax could be:

module M -- exported instances ( instance Monad T , instance Functor (F a) hiding (Functor (F Int), Functor (F Char)) , F(..) ) where import Foo (instance Monad a hiding Monad Maybe) data T a data F a b

## [edit] 3 Typeclass synonyms

This is needed for the same reason that we need type synonyms: to make complex types managable.

See http://repetae.net/john/recent/out/classalias.html.

### [edit] 3.1 Superclass defaults

The above propsal handles two separate issues, contexts with lots of class names, and defaults. The compatible superclass defaults propsal separates these two issues.

## [edit] 4 Extensible superclasses

This increases modularity by allowing us to add a new superclass to a class without modifying the class itself, just as at present we can always add new subclasses.

See http://taichi.ddns.comp.nus.edu.sg/taichiwiki/GPHomePage for a motivating example.

More details can be found in the paper *Modular Generic Programming with Extensible Superclasses*, available in ps format from
http://www.comp.nus.edu.sg/~sulzmann/publications/wgp06-modulargeneric.ps or in pdf from http://users.ox.ac.uk/~wolf2335/publications/generic.pdf.