TypeFamilies vs. FunctionalDependencies & type-level recursion

[Dan Doel]

On Wed, Jun 15, 2011 at 3:25 AM, Simon Peyton-Jones
<simonpj at microsoft.com> wrote:
> Wait.  What about
>        instance C [a] [b]
> ?  Should that be accepted?  The Coverage Condition says "no", and indeed it is rejected. But if you add -XUndecidableInstances it is accepted.

This 'clearly' violates the functional dependency as well.

However, I must admit, it surprises me that GHC or Hugs ever detected
this, and I imagine there's no general way to detect 'acceptable'
instances.

> Do you think the two are different?  Do you argue for unconditional rejection of everything not satisfying the Coverage Condition, regardless of flags?

One obvious difference from the instances that appear (depending on
how smart you're pretending to be as a compiler) bad but are
nevertheless okay is that these have no contexts. If you can detect
that, then:

    instance C a b
    instance C [a] [b]

clearly have multiple independent instantiations on both sides, and so
the relation is clearly non-functional. A simple heuristic might be to
reject those, but allow:

    instance (..., D .. b .., ...) => C a b

trusting that the context determines b in the right way. Is this
possibly what GHC used to do? Of course, that allows 'Show b => C a b'
so it's pretty weak.

A slightly more intelligent heuristic might be to see if the fundeps
in the context determine b, but that sounds like it might be leaving
the realm of what's checkable.

-- Dan