[Haskell-cafe] CRIP: the Curiously Reoccuring Instance Pattern

Ryan Ingram ryani.spam at gmail.com
Tue Jul 31 03:38:31 CEST 2012

With apologies to Jim Coplien :)

I've been seeing this pattern in a surprising number of instance
definitions lately:

instance (a ~ ar, b ~ br) => Mcomp a ar b br [1]
instance (b ~ c, CanFilterFunc b a) => CanFilter (b -> c) a [2]

The trick is that since instance selection is done entirely on the instance
head, these instances are strictly more general than the ones they replace:

instance Mcomp a a b b
instance CanFilterFunc b => CanFilter (b -> b) a

The compiler has to do a lot more work to select these instances; it has to
prove that the matching types actually match before it can select the
instance; if it can't, it won't select an instance, and instead will
complain about no instance "CLASS Int a".  But with the CRIP, you help the
compiler--it chooses the general instance, and then gets a constraint to
solve.  The constraint forces the two types to unify, or else there is a
type error.

What I'm wondering is--are there many cases where you really want the
non-constraint-generating behavior?  It seems like (aside from contrived,
ahem, instances) whenever you have instance CLASS A B where A and B share
some type variables, that there aren't any valid instances of the same
class where they don't share the types in that way.  For example, I've
never really seen a class in practice with instances like

class Foo a b
instance Foo a a
instance Foo ConcreteTypeA ConcreteTypeB

Note that it's very difficult to use polymorphic types in the second
instance without risking overlap.

TL;DR: I, for one, welcome our new type equality constraint overlords.

  -- ryan

[1] http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/99611
[2] http://www.yesodweb.com/blog/2012/07/classy-prelude
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120730/63fb5893/attachment.htm>

More information about the Haskell-Cafe mailing list