[Hugs-users] FunDeps: divergent improvement from overlapping instances

[Anthony Clayden]

> A precondition is that it scans instances in most-specific-first sequence
> -- which Hugs is already doing.

It galled me that going only by (an adapted notion of) overlap, I still had
to write three instances for a three-FunDep AddNat:

> class AddNat x y z | x y -> z, x z -> y, y z -> x
>
> instance AddNat Z Z Z
> instance AddNat Z (S y') (S y')
>
> instance AddNat x' y z' => AddNat (S x') y (S z')
>

because the 'obvious' way to write, with two instances (see below), put
them in no substitution ordering for the argument positions to the third
FunDep. So I dug out an idea from a few years ago (rejected proposal) and
implemented:

> instance  AddNat Z y y
>
> instance AddNat x' y z' => AddNat (S x') y (S z') | y /~ (S z')
>

That after the `|` in the instance is an 'Instance Disequality Guard':
prefer a more specific instance if those two types from the head unify.

Then Hugs puts that instance later in the preference ordering than the
first instance -- because the instance heads unify going by the argument
positions, but the first instance has no guard.

This also works for the semi-overlap instances that Hugs currently
rejects/GHC accepts but might turn out to be unusable:

>    class Semi a b
>
>    instance Semi Int b
>    instance Semi a   Bool  | a /~ Int
>
>    [W] Semi Int Bool             -- GHC currently rejects as ambiguous

The guard says: in case of [W] Semi Int Bool, prefer the Semi Int b
instance. We can even go:

>    instance Semi Int Bool
>
>    instance Semi Int b     | b /~ Bool
>    instance Semi a   Bool  | a /~ Int
>
>    instance Semi a  b             -- no guard, because strictly more
general than any instance
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/hugs-users/attachments/20220812/cee4f324/attachment.html>