flexible contexts and context reduction

[Tom Schrijvers]

On Wed, 26 Mar 2008, Ganesh Sittampalam wrote:

> On Wed, 26 Mar 2008, Ross Paterson wrote:
>
>> On Wed, Mar 26, 2008 at 08:52:43PM +0000, Ganesh Sittampalam wrote:
>>> I'm a bit confused about why the following program doesn't compile (in
>>> any of 6.6.1, 6.8.1 and 6.9.20080316). Shouldn't the Ord (a, b) context
>>> be reduced?
>> 
>> To use bar, you need (Ord a, Ord b).  You're assuming that Ord (a, b)
>> implies that, but it's the other way round.

Logically, the implication holds. There's an equivalence:

 	Ord a /\ Ord b <=> Ord (a,b)

Why it does or doesn't work in a Haskell impelmentation iss an 
implementation issue / language design issue.. There's a paper by Martin 
Sulzmann about extensible superclasses, which shows how this can be 
implemented if you don't use dictionaries for your typeclasses, but the 
type-passing scheme.

The problem with dictionaries is that you have to store the superclass 
dictionaries, here Ord a and Ord b, in the dictionary, here Ord (a,b).
However, what superclass dictionaries you have to store depends on the 
instance, e.g. Ord Int doesn't have any superclass and Ord [a] has 
superclass Ord a.


There maybe wasn't an easy solution, but here is my idea of how to 
to it with data or type families. The dictionary type would be:

 	data OrdDict a =
 		{ (<) :: a -> a -> Bool
                 , ...
 		, super :: Super a
 		}

 	type family Super a :: *
 	type instance Super Int   = ()
 	type instance Super [a]   = OrdDict a
 	type instance Super (a,b) = (OrdDict a, OrdDict b)

A similar solution is possible with a data family Super (but obviously I'm 
in favor of type families :) The openness of the family matches the 
openness of the type classes.

There is a little overhead in carrying around the superclasses.

Now ask your favorite Haskell system to implement this feature :)

Tom

--
Tom Schrijvers

Department of Computer Science
K.U. Leuven
Celestijnenlaan 200A
B-3001 Heverlee
Belgium

tel: +32 16 327544
e-mail: tom.schrijvers at cs.kuleuven.be
url: http://www.cs.kuleuven.be/~toms/