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

[oleg at okmij.org]

Ryan Ingram wrote:
> 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]

And here are a few more earlier instances of the same occurrence:

	http://okmij.org/ftp/Haskell/typecast.html

> 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.

Instances of the form
	class C a b
	class C a a
	class C a b
are very characteristic of (emulation) of disequality
constraints. Such instances occur, in a hidden form, all the time in
HList -- when checking for membership in a type-level list,
for example. There are naturally two cases: when the sought type is at
the head of the list, or it is (probably) at the tail of the list. 

	class Member (h :: *) (t :: List *)
	instance Member h (Cons h t)
	instance Member h t => Member h (Cons h' t)

Of course instances above are overlapping. And when we add functional
dependencies (since we really want type-functions rather type
relations), they stop working at all. We had to employ work-arounds,
which are described in detail in the HList paper (which is 8 years old
already).