*Simon Peyton-Jones* simonpj at microsoft.com
(C String) has (C Int) as a superclass. So the two instances are mutually recursive, but that's ok. That is not unreasonable. But it is dangerous. Consider class C [a] => C a Then any dictionary for (C a) would contain a dictionary for (C [a]) which would contain a dictionary for C [[a]], and so on. Haskell is lazy so we might even be able to build this infinite dictionary, but it *is* infinite. It's a bit like the "recursive instance" stuff introduced in "Scrap your boilerplate with class". After 5 mins thought I can't see a reason why this could not be made to work. But it'd take work to do. If you have a compelling application maybe you can open a feature request ticket, describing it, and referring this thread? Has anyone else come across this?
Yes. This is actually an active problem for me in my 'algebra' package. We can define additive, additive abelian and multiplicative semigroups: class Additive m where (+) :: m -> m -> m class Additive m => Abelian m class Multiplicative m where (*) :: m -> m -> m then we can define semirings (in the semirings are semigroups with distributive laws sense): class (Additive m, Abelian m, Multiplicative m) => Semiring m then to define monoids, we enforce the fact that every additive monoid is a module over the naturals. class (Semiring r, Additive m) => LeftModule r m where (.*) :: r -> m -> m class LeftModule Natural m => Monoidal m where This makes it an obligation of anyone that provides a Monoidal instance to ensure that they also supply the LeftModule, side-stepping what would be a hugely overlapping instance, and ensuring we can rely on it. But we weren't able to exploit the fact that any Additive semigroup forms a module over N+, due to the cycle. Moreover, we also weren't able to encode that every semiring is a module over itself. If we could have superclass cycles, we could restate this all as class LeftModule Whole m => Additive m where (+) :: m -> m -> m class Additive m => Abelian m class (Semiring r, Additive m) => LeftModule r m where (.*) :: r -> m -> m class Multiplicative m where (*) :: m -> m -> m class LeftModule Natural m => Monoidal m where zero :: m class (Abelian m, Multiplicative m, LeftModule m m) => Semiring m class (LeftModule Integer m, Monoidal m) => Group m where recip :: m -> m class Multiplicative m => Unital m where one :: m class (Monoidal r, Unital r, Semiring r) => Rig r where fromNatural :: Natural -> r fromNatural n = n .* one class (Rig r, Group r) => Ring r where fromInteger :: Integer -> r fromInteger n = n .* one ... There are a number of typeclass cycles in there, but I can safely instantiate the whole mess without any overlapping instances and I already have to ball all of these classes up in the same 'Internals' module to avoid orphans instances anyways. Using the usual dodge of a newtype to provide Self module over any given semiring is particularly unsatisfying because the Natural and Integer multiplication become horrific, and I wind up having to multiply the code below this point in the hierarchy to deal with the 'self algebra' cases. =/ I've also run into the problem about once or twice a year when encoding other concepts that are usually more categorical in nature. I would love to be able to do this. -Edward Kmett