[Haskell-cafe] Overlapping Instances with Functional Dependencies

[Simon Peyton-Jones]

Martin's dead right.  GHC uses a less sophisticated mechanism to do
matching when it's thinking about functional dependencies than when it's
doing straight instance matching.  Maybe something cleverer for fundeps
would make sense, as you point out.  I hadn't thought of that before;
it's a good point.

Nowadays, whenever a fundep question comes up I think "how would it show
up if we had associated type synonyms instead of fundeps?" (see the
paper on my home page).  In this case I think the answer is "GHC's
current instance-matching mechanism would work unchanged"; or to put it
another way, what ever mechanism is used for instance matching, the same
would be used for type dependencies.

Simon
  
| I wouldn't call this a bug, overlapping instances
| and in particular the combination with functional dependencies
| are something which is not well studied yet.
| Hence, GHC is very conservative here.
| 
| I feel like you, this program should work.
| As you correctly point out, there's a conflict among the
| two improvement rules (resulting from the instances and FD).
| A sensible decision is to apply the same "ad-hoc"
| mechanism to improvement rules that is currently
| applied to overlapping instances. Of course, we need some
| formal system to express such conditions precisely.
| You find some hints how to achieve this in
| 
| G. J. Duck, S. Peyton-Jones, P. J. Stuckey, and M. Sulzmann.
| Sound and decidable type inference for functional dependencies.
| In Proc. of ESOP'04
| 
| Martin
| 
| 
| Daniel Brown writes:
|  > I have the following three programs:
|  >
|  >    class Foo a b
|  >    instance Foo (a -> b) (a -> [b])
|  >    instance Foo a a
|  >
|  >    class Bar a b | a -> b
|  >    instance Bar (a -> b) (a -> b)
|  >    instance Bar a a
|  >
|  >    class Baz a b | a -> b
|  >    instance Baz (a -> b) (a -> [b])
|  >    instance Baz a a
|  >
|  > When compiled in ghc 6.4 (with -fglasgow-exts
|  > -fallow-overlapping-instances -fallow-undecidable-instances) Foo
|  > and Bar compile fine, but Baz fails with this error:
|  >
|  >    Baz.hs:2:0:
|  >        Functional dependencies conflict between instance
declarations:
|  >          Baz.hs:2:0: instance Baz (a -> b) (a -> [b])
|  >          Baz.hs:3:0: instance Baz a a
|  >
|  > This is how I interpret the error: The fundep says "a uniquely
|  > determines b", but if you have `Baz (Int -> Int) b`, b is `Int ->
[Int]`
|  > according to the first instance and `Int -> Int` according to the
second
|  > instance. b isn't uniquely determined by a, so the functional
dependency
|  > isn't functional -- thus the conflict.
|  >
|  > When confronted with overlapping instances, the compiler chooses
the
|  > most specific one (if it is unique), e.g. `Baz (a -> b) (a -> [b])`
is
|  > more specific than `Baz a a`.
|  >
|  > But it seems that the combination of the two features is broken: if
the
|  > most specific instance is chosen before checking the functional
|  > dependency, then the fundep is satisfied; if the fundep is checked
|  > before choosing the most specific instance, then it isn't.
|  >
|  > Is this a bug, or am I confused?
|  >
|  >   Dan
|  > _______________________________________________
|  > Haskell-Cafe mailing list
|  > Haskell-Cafe at haskell.org
|  > http://www.haskell.org/mailman/listinfo/haskell-cafe
| _______________________________________________
| Haskell-Cafe mailing list
| Haskell-Cafe at haskell.org
| http://www.haskell.org/mailman/listinfo/haskell-cafe