View source for Comparing class alias proposals

[http://repetae.net/recent/out/classalias.html John Meacham's proposal] for type class aliases has been around for a few years now. It has not been implemented yet; instead, several variations to his original proposal have come up. In this document we collect those ideas and their motivations in a hopefully clear overview. We also point out potential pitfalls or things that need more pondering: many ideas look very attractive and promising but prove troublesome when made formal. We believe this is the main reason they haven't been implemented yet.

For each idea we give a motivation from the point of view of a stakeholder. We identify three stakeholders:
* the designer of a class or class hierarchy;
* the author of class instances;
* the programmer using the classes and instances.

Furthermore, most motivations can be grouped into two categories:
* increasing the flexibility of the class system, useful when designing new API;
* changing an existing API while maintaining backwards compatibility.

== List of proposals ==

We've found the following documents that propose extensions or variations of the original proposal:

* [http://repetae.net/recent/out/classalias.html John Meacham's original proposal]
* [[Context alias]]
* [[Superclass defaults]]
* [[Class system extension proposal]]
* GHC ticket 788: [http://hackage.haskell.org/trac/ghc/ticket/788 Class aliases]
* [http://tomschrijvers.blogspot.com/2009/11/haskell-type-constraints-unleashed.html Constraint synonyms]

== Context synonyms ==

The most basic idea is that of a context synonym (CS):

 context BoundedEnum a = (Bounded a, Enum a)
 context SatisfyA f s = (Satisfy f, Alternative f, Input f ~ s)

A context synonym may appear anywhere a context is allowed:
* in the type signature of a function;
* in a data type or constructor;
* in a superclass constraint.

The arguments to a CS have to be kind-checked. In the examples above:
 Bounded, Enum, BoundedEnum :: * -> Context
 Satisfy, Alternative :: (* -> *) -> Context
 Input :: (* -> *) -> *
 SatisfyA :: (* -> *) -> * -> Context

Context synonyms are synonymous and interchangable with their right-hand sides, much like type synonyms. They are distinct from class aliases in that they do not define any new classes (dictionaries), functions or defaults. Ideally, they can be exported and documented, just like type synonyms.

'''Motivation''': CS's are useful when a particularly long context keeps popping up, something that often happens when type-level programming is applied, for example with generic programming. They are interesting for programmers using already existing classes.


== Higher-order context synonyms ==

Possible additions to the context synonyms include:

'''Q''': May a CS's RHS refer to other CS's? For example:

 context Foo a = (BoundedEnum a, Eq a, Ord a)

This introduces the possibility of loops. Should loops be forbidden? It could be argued that in some cases of loops, the CS's transitive closure should be used, but this is only acceptable if the closure is finite. It seems more elegant to just forbid all loops.

'''Q''': Apart from type constructors, may a CS's variables be class constructors (things of kind ... -> Context) as well? For example:

 context Bar a = a Int

Here Bar :: (* -> Context) -> Context

'''Q''': May CS's be passed as arguments to other CS's? For example:

 context Biz = Bar BoundedEnum

'''Q''': May CS's be partially applied? Consider these alternate definitions of BoundedEnum:

 context BoundedEnum a = (Bounded, Enum) a
 context BoundedEnum = (Bounded, Enum)

Currently the <code>,</code> separator can be seen as having kind <code>Context -> Context -> Context</code>, but the example above would make this more generic: <code>k -> k -> k</code>.

'''Motivation''': these ideas are direct extensions of context synonyms and are useful for clients.


== Instances of class aliases ==

One of John Meacham's main reasons for his proposal is the lack of possibilities for abstraction in the current class system: "there is no way to hide the fact that you changed a class hierarchy", he writes. Therefore, he introduces the possibility of writing instances of ''class aliases'':

 class alias Num a = (Additive a, AdditiveNegation a, Multiplicative a, FromInteger a)
 
 instance Num a where
   zero        = ...
   (+)         = ...
   (-)         = ...
   negate      = ...
   one         = ...
   (*)         = ...
   fromInteger = ...

'''Motivation''': Class designers can now later split up a class in smaller classes if they redefine the initial class as a class alias for the new, smaller type classes. More specifically, this could solve the Num hierarchy problem: how to redefine the Num-related type classes in the prelude while maintaining backwards compatibility?

John's example above introduces new functions <code>zero</code> and <code>one</code> which conflicts with the idea of splitting up Num in strict subclasses. However, this problem is (supposedly?) solved by overriding superclass defaults; see below. Also, <code>signum</code> and <code>abs</code> are not present in the example, but they may be added to the appropriate subclasses.

John's proposal can be decomposed into two smaller steps:
* being able to write one instance header for several instances at the same time
* then replacing the several type classes by a class alias.

'''Q''': What if an instance header expands to several instances of the same class?

For example, a class alias instance could expand to:

 instance (Functor [], Functor Maybe) where
   ...

Then multiple <code>fmap</code>s need to be defined. Which is which?

'''Q''': What if an instance is made of several classes with overlapping function names?

Currently function definitions in a class may not be qualified; only the class name in instance header may be qualified. Being able to write several instances under one header introduces naming problems in this case.

'''Q''': What if a class alias expands to many classes, of which one already has an instance in scope?

Should we forbid such an instance and force the programmer to expand the class alias manually to all classes except the one of which there is an instance of already?

Or should such an instance still be allowed, but the implementation of the violating class be forbidden? It seems like a bad idea to allow this without making such an omission clear and explicit in the syntax.

=== Class alias or context synonym? ===

Can class aliases as used above be read as "context synonyms"?

Clearly there are many differences between the two. Their intended uses are originally different. Should they be two different things instead?

Class aliases (in the case of writing instances of them) seem like a strict subset of context synonyms. If class aliases are to piggyback on context synonyms, then we need to think carefully about what form such a context synonym should have for instances to make sense.
== Overriding superclass defaults ==

=== In normal type classes ===

Consider:

 class Functor f => Applicative f where
   pure :: a -> f a
   (<*>) :: f (a -> b) -> f a -> f b

In current Haskell, the header means two things:
* if you want to write an instance of <code>Applicative</code>, your type should already be an instance of <code>Functor</code>;
* wherever a constraint (dictionary requirement) <code>Applicative</code> appears, a constraint <code>Functor</code> is implied.

However, such a superclass constraint is often added to mean: if a type is <code>Applicative</code>, then we trivially have an instance of <code>Functor</code> (namely by defining <code>fmap = (<*>) . pure</code>). Sadly, there is no way to automate this in Haskell; programmers still have to define explicit instances for <code>Functor</code>. The following comes close:

 instance Applicative f => Functor f where
   fmap = (<*>) . pure

Except this doesn't work well with the way instances are resolved now: the head of the instance basically says: ''any type'' is a Functor. The superclass constraint isn't checked until after the irrevocable match has been made.

[[Class system extension proposal]] suggests something like the following to fix this issue:

 class Functor f => Applicative f where
   pure :: a -> f a
   (<*>) :: f (a -> b) -> f a -> f b
 
   fmap = (<*>) . pure

I.e. allow a class to provide or override default implementations of functions from superclasses. This means that writing an instance of Applicative implies also writing an instance of Functor. What should happen if there already is an instance of Functor in scope?

=== In context aliases ===

== Adding new functions ==

Some documents propose allowing adding new functions to a type class alias.

'''Q:''' How is this different from a normal type class?

A critical idea in class aliases is that instances can exist implicitly because there exist instances of all an alias' superclasses. When new functions are introduced in a class alias this can no longer be true. In such cases, what is the added value of type class aliases? They no longer behave differently from normal type classes.