[Haskell-cafe] Overlapping/Incoherent instances

[Sean Leather]

> As part of a project to formalize the theory of overlapping instances,
> I'm looking for examples of overlapping and incoherent instances and
> their usage.


EMGM [1] uses overlapping instances to make it more convenient to use
extensible, generic functions on arbitrary datatypes. They're not absolutely
necessary, but they save on (a potentially large amount of) boilerplate
code.

For example, we have a generic show function [2], but without extension it
would evaluate a list value as:

> show [1,2,3 :: Int]
"1:2:3:[]"

We want to print a list with the traditional Haskell syntax, so we need to
extend 'show' with a special case. Without overlapping instances, we would
do it like this:

> class (Generic g) => GenericList g where
>   rlist :: g a -> g [a]
>   rlist = rList

(where 'rList' is the list representation [3])

> instance GenericList Show where
>   rlist = specialListShow

(where 'specialListShow' is our specialization)

> instance (GenericList g, Rep g a) => Rep g [a] where
>   rep = rlist rep

(where 'Rep g a' is the type class dispatcher for representations and 'rep'
is the value that determines that representation)

The problem with the above is that if one potentially wants to write an
ad-hoc case for any datatype/function pair, then we need to have a class
like 'GenericList' for every datatype. Then, we can write an instance of
'GenericList' for that function (e.g. 'show'). However, even if we don't
want a special case, we still need that instance. Supposing we wanted to use
'show' as is for lists in our program, then we need a instance with
defaults.

> instance GenericList Show

It's not very convenient to use generic functions if one must keep declaring
instances for every datatype and function combination that one uses.
Overlapping instances to the rescue!

With overlapping instances enabled, we remove the 'GenericList' class and
instance from above and change the 'Rep' instance to use 'Generic' (our
"base" class) instead of 'GenericList'.

> instance (Generic g, Rep g a) Rep g (List a) where
>   rep = rlist rep

Then, nothing else needs to be done to use 'show' on any datatype supported
by EMGM or with support added by the user. If one still wants to define an
ad-hoc case for lists, it's just as simple.

> instance (Rep Show a) => Rep Show (List a) where
>   rep = specialListShow rep

I would point you to our lecture notes for the Advanced Functional
Programming Summer School that give a better explanation, but they're not
quite done. Let me know if you want more information off-list.

Regards,
Sean

[1] http://www.cs.uu.nl/wiki/GenericProgramming/EMGM
[2]
https://svn.cs.uu.nl:12443/viewvc/dgp-haskell/EMGM/src/Generics/EMGM/Functions/Show.hs?view=markup
[3]
https://svn.cs.uu.nl:12443/viewvc/dgp-haskell/EMGM/src/Generics/EMGM/Data/List.hs?view=markup
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081013/151e0922/attachment.htm