[Haskell-cafe] Functional dependencies with Type Classes

[Manuel M T Chakravarty]

Henning Günther:
> suppose there are two (identical) classes:
>
>> class Res a b | a -> b  where
>> 	getRes :: a -> b
>
> and
>
>> class Res2 t where
>> 	type Member t
>> 	getRes2 :: t -> Member t
>
> It is easy to automatically make every instance of Res2 an instance of
> res:
>
>> instance Res2 a => Res a (Member a) where
>> 	getRes x = getRes2 x
>
> However, declaring every instance of Res an instance of Res2 seems
> impossible, as the following doesn't compile
>
>> instance Res a b => Res2 a where
>> 	type Member a = b
>> 	getRes2 x = getRes x
>
> Question is: How to do this? The reason I need it is because I use a
> library which uses functional dependencies, but my classes shall be  
> type
> families.

The last definition is invalid as the right-hand side of a type family  
instance can only depend on its parameters.  However, in

   type Member a = b

you pull 'b' out of thin air.  Remember that associated types (ie,  
type families as part of classes) are only syntactic sugar for sparate  
type family and class declarations.  Obviously, it would be imposible  
to pull the type instance out of the class in your definition.  (The  
mismatch between FDs and TFs here really is due to FDs being tied to  
classes and TFs being separable - in that sense TFs are more general  
than FDs, and hence, you cannot always simulate TFs with FDs.)

However, you can wrap an FD library into a TF interface with some  
additional effort.  Using your example for illustration, define the  
type family and class separately:

   type family Member a
   class Res2 a where
     getRes2 :: a -> Member a

Then, implement the catch all class instance as follows:

   instance Res a (Member a) => Res2 a where
     getRes2 x = getRes x

(This needs -fundecidable-instances.  It is perfectly decidable if  
your FD class is, but GHC doesn't know that.)

Now, the additional overhead is that you need to define the type  
family instances separately; ie, for every class instance of the FD  
class, such as

   instance Res Int Bool where
     getRes x = x == 0

you need to repeat the type mapping:

   type instance Member Int = Bool

I hope this is not too much of a burden in your application.

Manuel

PS: Hmm, maybe this should go onto the wiki...