Version 2 (modified by chak, 10 years ago) (diff)


Class Families

Our translation of data families in combination with the desugaring of classes into data types suggest the idea of indexed class families, which turns out to be rather useful for generalising class APIs for commonly used data structures.

An example

As a motivating example take the following problem from John Hughes' Restricted Data Types. Suppose we want to implement a set API as a type class. Then, we find that the signature

insert :: Set s => a -> s a -> s a

is too general. We need additional type constraints whose exact form depends on the type constructor we use to construct the sets; i.e., it varies on an instance by instance basis. For lists, we just need Eq, but for sets as finite maps, we need Ord.

With indexed class families, we can define a set class as follows:

class Set s where
  class C s a
  empty  :: s a
  insert :: C s a => a -> s a -> s a

Here, the associated class C of Set is indexed by the class parameter s.

In instances for sets as lists

instance Set [] where
  class Eq a => C [] a
  empty = []
  insert x s | x `elem` s = s
             | otherwise  = x:s
instance Eq a => C [] a

and sets as finite maps

newtype MapSet a = MapSet (Data.Map.Map a ())
instance Set MapSet where
  class Ord a => C MapSet a
  empty = Data.Map.empty
  insert x s = Data.Map.insert x () s
instance Ord a => C MapSet a

we instantiate C differently for different type indexes. The class family instances have no members in this case, but use existing classes as a superclass to supply insert with the equality and ordering methods, respectively. As we want to use these superclasses for sets of any element type of which we have an instance of the superclasses, we need a catch-all instance for each class instance. That is somewhat ugly especially, as it requires the use of -fallow-undecidable-instances.