[Haskell-cafe] HEq and Context reduction stack overflow, non
optimal ghc behaviour ?
wren ng thornton
wren at freegeek.org
Fri Aug 29 04:29:18 EDT 2008
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.
More information about the Haskell-Cafe