Overlapping/Incoherent instances
Hello everyone, 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. One such example would be the old version of the Monad Transformer Library, which used overlapping instances together with MonadTrans. Any other examples or suggestions would be greatly appreciated! Thanks, /g
J. Garrett Morris wrote:
Hello everyone,
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. One such example would be the old version of the Monad Transformer Library, which used overlapping instances together with MonadTrans. Any other examples or suggestions would be greatly appreciated!
I use overlapping instances extensively with my (unpublished) work on heterogeneous and extensible unification. In particular, the portion based on Swierstra's _Data Types a la Carte_[1]. I'm sure other folks have been using DTalC for interesting projects as well. [1] http://wadler.blogspot.com/2008/02/data-types-la-carte.html -- Live well, ~wren
jgmorris:
Hello everyone,
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. One such example would be the old version of the Monad Transformer Library, which used overlapping instances together with MonadTrans. Any other examples or suggestions would be greatly appreciated!
Though I note mtl doesn't actually list OverlappingInstances in its .cabal file, MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances, TypeSynonymInstances Now, this is *exactly* why having 'haskell prime' flags for this pays off. Researches can now go and inspect all of http://hackage.haskell.org for particular language features. A quick, ad hoc search reveals, for the "OverlappingInstances" flag, (some of these may only mention it in docs or in test suites), anydbm-1.0.5 AutoForms-0.4.2 cedict-0.2.5 cgi-undecidable-3000.0.0 ConfigFile-1.0.4 conjure-0.1 darcs-buildpackage-0.5.12 datapacker-1.0.1 DBus-0.4 dfsbuild-1.0.2 emgm-0.1 fgl-5.4.1.1 ForSyDe-3.0 ftphs-1.0.4 generic-xml-0.1 gopherbot-0.1.0 Graphalyze-0.3 HAppS-Data-0.9.2.1 HAppS-IxSet-0.9.2.1 HAppS-Util-0.9.2.1 haskeline-0.3.2 haxr-3000.1.1.1 haxr-th-3000.0.0 HDBC-1.1.5 HDBC-postgresql-1.1.4.0 HDBC-sqlite3-1.1.4.0 hgalib-0.2 hg-buildpackage-1.0.4 hjs-0.2.1 HJScript-0.4.4 HList-0.1 hoogle-4.0.0.5 hpodder-1.1.5 HSH-1.2.6 HsJudy-0.2 hslogger-1.0.6 hsp-0.4.4 HsParrot-0.0.2 HsPerl5-0.0.6 hstidy-0.2 HStringTemplate-0.4 hsx-0.4.4 hsx-xhtml-0.4.4 ivor-0.1.5 libGenI-0.16.1 ListLike-1.0.1 logfloat-0.9.1 microbench-0.1 MissingH-1.0.2.1 monad-param-0.0.2 parsely-0.1 PostgreSQL-0.2 pugs-compat-0.0.5 pugs-DrIFT-2.2.3.0 RJson-0.3.5 scenegraph-0.1 sessions-2008.7.18 srcinst-0.8.10 StrategyLib-4.0.0.0 syb-with-class-0.4 Takusen-0.8.3 TV-0.4 twidge-0.99.3 TypeCompose-0.5 uvector-0.1.0.3 Wired-0.1.1 For IncoherentInstances, we have a fair few less, hjs-0.2.1 HsJudy-0.2 hgalib-0.2 TV-0.4 AutoForms-0.4.2 HsPerl5-0.0.6 IOR-0.1 hoogle-4.0.0.5 hstidy-0.2 uvector-0.1.0.3 pugs-DrIFT-2.2.3.0 Note that at least for 'uvector' the flags are used in the testsuite. Also, packages may well use these extensions, but only implicitly (if they're enabled by more general flags, like -fglasgow-exts) -- Don
Don Stewart wrote:
A quick, ad hoc search reveals, for the "OverlappingInstances" flag, (some of these may only mention it in docs or in test suites),
[...] logfloat-0.9.1
Ah yes, logfloat is using them too, for some of the auxiliary stuff. * PartialOrd was designed to fix certain brokennesses of the Prelude's Ord. Naturally any totally ordered type is also partially ordered, so we'd like to have |Ord a => PartialOrd a| with the obvious implementation[1]. However the Ord instances for Float and Double are lies because of NaN values. I derive the |Ord a => PartialOrd a| instance because I'm a bad little Haskeller who wanted to make things easier for users of the library. This usage of OverlappingInstances seems fairly common when people introduce new classes to the hierarchy, particularly when they are relaxing requirements of the official classes. That is, there are some default implementations we'd like to give but cannot for some reason, and OverlappingInstances allows us to give them. * Transfinite uses it for similar reasons to fix brokenness of the realToFrac function when converting transfinite values into the Rational type. That is, |Transfinite a => RealToFrac a Rational| is not inhabitable for any |a| since Rational cannot absorb transfinite values. Both of these seem like good changes for haskell' in order to correct the behavior of Float and Double (and because there are many more partially ordered types than totally ordered ones). Alas I've not had a chance to file the suggestions. [1] Given that Ord is more popular. Conversely, if the Prelude is changed, we may wish to require PartialOrd for all Ord instances, and thing give Ord a default implementation that removes the Just from the PartialOrd versions. -- Live well, ~wren
On Sun, Oct 12, 2008 at 2:12 PM, Don Stewart
Though I note mtl doesn't actually list OverlappingInstances in its .cabal file,
Indeed - MTL seems to have been rewritten at some point in the past to prefer exhaustive enumeration to overlap. Thank you for the other suggestions! Presumably this also doesn't cover if they're enabled by LANGUAGE pragmas in individual files? /g -- I am in here
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/Functio... [3] https://svn.cs.uu.nl:12443/viewvc/dgp-haskell/EMGM/src/Generics/EMGM/Data/Li...
participants (5)
-
Don Stewart -
J. Garrett Morris -
Marc Weber -
Sean Leather -
wren ng thornton