Marc Weber wrote:
Now ghc can try to resolve (1),(2),(3) in arbitrary order.. What happens if ghc starts with (3)? It tries to find an instance for not known types.. Damn. There is even a matching instance.. , the same one. This time it starts even with HEq <unkown> <unkown> <unkown> which is even more bad! after the second recursion it already knows that won't find a solution, because it will try to resolve HEq <unkown> <unkown> <unkown> again and again..
What happens if ghc starts with (1 or 2)? It happily finds an instance *and* it can even resolve elNr and elNr' Those can then be used to find an instance for (3) easily
So I think the behaviour of ghc should be changed to prefer resolving class constraints which reduce the amount of unkown types first
I even consider this beeing a bug ?
So maybe this thread should be moved to glasgow-haskell-users ?
There are a number of issues like this due to the fact that typeclass instances aren't determined by full SLD resolution. More particularly the determinism information in fundeps seems to be ignored in this whole process. Not that I'm a GHC hacker (yet), but research in this area is at the top of my to-do stack; alas that's still a ways away. To put a refinement on your proposal, I'd suggest that fundeps be used to construct a dataflow graph in order to know which instances to pursue first (namely, the leaves). To resolve the ordering any toposort of the dataflow graph should be fine. This still has the problem of if there's no toposort, though: class Foo a b | a -> b class Bar a b | b -> a class Wtf a b instance (Foo a b, Bar a b) => Wtf a b There are a few standard approaches to break the cycle, though if instances of Foo or Bar are given inductively we might run into the same problems as your code. Here's another proposal, and perhaps an easier one to hack together for the time being. When pursuing the context of an instance for some class A, resolve all instances for non-A classes before pursuing instances for A. It's not a general solution, but it's closer to correct at least. -- Live well, ~wren