A fundep bug (?)

[Jeffrey R. Lewis]

anatoli wrote:

> This slightly bizarre (meta)code has to do with
> the recent Dimension thingy, discussed on
> haskell mailing list.
>
> > data Z = Z
> > data S a = S a
>
> > z = Z
> > sz = S Z
> > ssz = S (S Z)
>
> > class Add a b c | a b -> c where add :: a -> b -> c
>
> > instance Add Z a a
> > instance Add a b c => Add (S a) b (S c)
>
> > class Mul a b c | a b -> c where mul :: a -> b -> c
>
> > instance Mul Z a Z
> > instance (Mul a b c, Add b c d) => Mul (S a) b d
>
> > data Q a b = Q a b
>
> Problem here.  This is the addition of rational
> numbers: (a/b) + (c/d) = (ad+bc)/bd
>
> > instance (Mul a d ad,
> >           Mul b c bc,
> >           Mul b d bd,
> >           Add ad bc ad_bc) => Add (Q a b) (Q c d) (Q ad_bc bd)
>
> The problem is, Hugs does not infer a predicate-free type for
> say "add (Q sz sz) (Q sz sz)". I think it's a Hugs bug.
> I tried both CVS and last stable versions.
>
> When I turn "Explain instance resolution" on, the last thing I
> get is:
>
>  entail: () ||- Add (S Z) (S Z) a
>   No instance found for Add (S Z) (S Z) a
>
> which is strange because the last parameter of Add
> functionally depends on the rest.
> --
> anatoli (at, not speaking for) ptc (dot) com

This looks like a bug that I've been aware of for a while, where context reduction isn't getting iterated enough to rattle out all of the functional dependencies.  I think this has an easy fix, and will take a look at it at some point.

--Jeff