[Haskell] Re: indirectly recursive dictionaries

[Simon Peyton-Jones]

[Redirecting to GHC users.]

| Tom Schrijvers wrote:
| > The cyclic dictionaries approach is a bit fragile. The problem appears to
| > be here that GHC alternates exhaustive phases of constraint reduction and
| > functional dependency improvement. The problem is that in your example you
| > need both for detecting a cycle.

The whole thing relies on "spotting a loop", and that's inherently a bit fragile. I don't know of any formal work on the subject, although I bet there is some.

GHC's current algorithm does not run functional dependencies sufficiently aggressively, because it treats fundeps a different kind of thing to class constraints.  Our new solver, long promised but still in the works, fully integrates type classes with type equalities (fundeps, type functions etc), and so should do a better job here.  Roughly speaking, the idea is to combine our ICFP'08 paper [1] with a type-class solver.  Since writing the ICFP'08 paper we have found some very useful simplifications; and we also have a new plan for the solving strategy "OutsideIn" [2].

That said, solving recursive problems is not our primary focus right now -- getting it working is -- so I can't promise that it'll do a better job, but I think it will.

| It seems we can convince GHC to do constraint reduction and
| improvement in the order we desire. The key is to use the
| continuation-passing style -- which forces things to happen in the
| right order, both at the run-time and at the compile time.

Oleg you are a master at persuading GHC's somewhat ad-hoc implementation to dance to your tune.  But it'd be better just to make the implementation more complete in the solutions it finds.  That's what we are working on now.

Simon

[1] http://research.microsoft.com/~simonpj/papers/assoc-types/index.htm
[2] http://research.microsoft.com/~simonpj/papers/gadt