Class constraints for associated type synonyms
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
From: Jan-Willem Maessen
Sent: Wed, March 23, 2011 8:43:14 PM
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:
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.
The conditions in the report are quite restrictive - in particular, the context must consist only of classes applied to type variables. When you used a multiparameter type class and an FD, the type you wanted to mention was just a type variable. http://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-750004.3 The GHC user's guide suggests FlexibleContexts should be enough to allow you to declare that class: http://www.haskell.org/ghc/docs/7.0-latest/html/users_guide/type-class-exten... FlexibleInstances seems only to affect what is allowed in an instance head. I don't see how it helps at all, unless it implies some other extensions. You might still run into termination issues - as a an associated type synonym rather than an associated data type, GeneratorOf a might very well be something large, and the conditions (disabled by UndecidableInstances) don't take advantage of the acyclic superclass relationship. http://www.haskell.org/ghc/docs/7.0-latest/html/users_guide/type-class-exten...
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.
Do you have any examples? I've always found FlexibleInstances alone unproblematic - it's only when you add OverlappingInstances or worse that things can get messy. Brandon
| 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. Suppose you have these wierd instances: type instance GeneratorOf (Tree a) = Tree (Tree a) instance Generable a => Monoid (Tree a) instance Generable (Tree a) Now, in the last of these we need to cough up an instance of Generable (Tree a)'s superclasses. Ah, that's Monoid (GeneratorOf (Tree a)) Ah, that's Monoid (Tree (Tree a)) We have an instance of Monoid, but it needs, well Generable (Tree a), which is where we started. If I'd nested things a bit more deeply you can see I'd get into an infinite regress. So you have to take responsibility that instance solving will terminate, hence FlexibleInstances. As you say, the same thing can happen with fundeps. The fact that the thing is allowed is probably a bug in the Fundep stuff. Simon
On Thu, Mar 24, 2011 at 11:36 AM, Simon Peyton-Jones
| 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.
Suppose you have these wierd instances: type instance GeneratorOf (Tree a) = Tree (Tree a) instance Generable a => Monoid (Tree a) instance Generable (Tree a)
Now, in the last of these we need to cough up an instance of Generable (Tree a)'s superclasses. Ah, that's Monoid (GeneratorOf (Tree a)) Ah, that's Monoid (Tree (Tree a)) We have an instance of Monoid, but it needs, well Generable (Tree a), which is where we started.
If I'd nested things a bit more deeply you can see I'd get into an infinite regress. So you have to take responsibility that instance solving will terminate, hence FlexibleInstances.
As you say, the same thing can happen with fundeps. The fact that the thing is allowed is probably a bug in the Fundep stuff.
Thanks, it's good to know that I was, in fact, being naughty in both instances (and not merely being constrained from doing Good Things by the typing rules for associated types). Back to the drawing board. -Jan
participants (3)
-
Brandon Moore -
Jan-Willem Maessen -
Simon Peyton-Jones