[Haskell-cafe] Class constraints for associated type synonyms

Jan-Willem Maessen jmaessen at alum.mit.edu
Thu Mar 24 02:43:14 CET 2011

Hi all -

I've been trying to construct a class declaration with an associated
type synonym, but I'd like to constrain that type to belong to a
particular class.

Consider the following class:

class Monoid m => Constructs c m | c -> m where
  construct :: m -> c

This captures the idea that the collection c ought to be constructed
using the monoid m (say if we're doing the construction using the
Writer monad)--the functional dependency indicates the desire for the
type c to injectively determine the choice of monoid m.  For example:

newtype ListBuilder a = Builder ([a] -> [a]) deriving (Monoid)

instance Constructs [a] (ListBuilder a) where
  construct (Builder f) = f []

instance (Ord a) => Constructs (Set a) (Set a) where
  construct = id

Now I'd like to be able to do the same thing using an associated type
synonym, something like this:

class Monoid (GeneratorOf a) => Generable a where
  type GeneratorOf a :: * -> *
  construct :: GeneratorOf a -> a

Now, it seems I need FlexibleInstances to do this when I'm using an
associated type synonym, but I don't need the flexibility when using a
multiparameter type class.  In both cases the instance constraint
involves types that can be injectively inferred (if I have my
terminology straight; work with me here) from a single type mentioned
in the class head.  In particular, I can imagine storing the
dictionary for Monoid (GeneratorOf a) in the dictionary for Generable
a, and thus allowing context reduction of (Monoid (GeneratorOf tyvar))
to (Generable tyvar).  Meanwhile, I think there are things that are
permitted by FlexibleInstances that I'd rather *not* have creeping
into my programs.

Is there a fundamental constraint I'm missing here that requires the
full generality of FlexibleInstances?  Do I need to use
FlexibleInstances whenever I use associated types in my programs?

-Jan-Willem Maessen

More information about the Haskell-Cafe mailing list