[Haskell-cafe] HEq and Context reduction stack overflow, non optimal ghc behaviour ?

[wren ng thornton]

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