[Haskell-cafe] Fundeps and overlapping instances

[Twan van Laarhoven]

On 24/05/12 14:14, AntC wrote:
> Simon Peyton-Jones<simonpj<at>  microsoft.com>  writes:
>
>> [from 7 Jul 2010. I've woken up this thread at Oleg's instigation
>> http://www.haskell.org/pipermail/haskell-prime/2011-July/003491.html ]
>>
>
> I'm not going to talk about Fundeps. This is about introducing overlapping
> instances into type families. But I mean dis-overlapped overlaps, with dis-
> equality guards on the instances:
> http://www.haskell.org/pipermail/haskell-prime/2012-May/003689.html
> This is essentially the same proposal as the July 2011 discussion, but a
> little updated with actual experience of type families in their more mature
> form.
>
> Example type family equations:
>          type instance F Int = Bool
>          type instance F a | a /~ Int = [a]  -- explicit dis-equality guard
>

Have you considered the alternative notation where multiple guards are allowed, 
as in normal function definitions? Something like:

     type instance F a
         | a ~ Int   = Bool
         | Otherwise = [a]

The last 'otherwise' clause is mandatory, matching should never fall through. 
Perhaps it could be an error if that were to happen, which would allow you to 
write closed type functions. Note that Otherwise could be declared in the library as
     type Otherwise = () :: Constraint

I think this variant is almost equivalent to your proposal (so maybe it's just 
bikeshedding). It is also very similar to the IFEQ proposal, and you can desugar 
one in terms of the other.

I also don't know how hard something like this would be to implement. The 
matching of type instances would be done in the same way as now, only their 
expanding is changed. The compiler will at this point have to look which guards 
are satisfied. In this example the first guard is a~Int, and this can not be 
checked until more is known about a. So, even though we have a known matching 
instance, it can not yet be expanded. Perhaps the notation "instance F a | a /~ 
Int" is better, because then a type family application can be expanded iff there 
is a matching instance.


Twan