Class constraints for associated type synonyms

[Jan-Willem Maessen]

On Thu, Mar 24, 2011 at 11:36 AM, Simon Peyton-Jones
<simonpj at microsoft.com> wrote:
> | 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