Multiparameter typeclasses and illegal instance declarations

Question

I made a version of the Convertible class like so:

class Convertible a b where
  convert :: a -> b

instance (Convertible a b, Functor f) => Convertible (f a) (f b) where
  convert = fmap convert

However, I found it annoying that I would have to make a new instance if I ever wanted to string two conversions together. So I tried adding this:

instance (Convertible a b, Convertible b c) => Convertible a c where
  convert = convert . convert

The compiler complained with this:

Variable ‘b’ occurs more often than in the instance head
  in the constraint: Convertible a b
(Use UndecidableInstances to permit this)
In the instance declaration for ‘Convertible a c’
Variable ‘b’ occurs more often than in the instance head
  in the constraint: Convertible b c
(Use UndecidableInstances to permit this)
In the instance declaration for ‘Convertible a c’

At this point I understand why the compiler is complaining at me, and I'd really rather not turn on UndecidableInstances. The way I currently have my instances set up, there's only one instance of Convertible a b for each a. I hoped that adding a functional dependency a -> b would alleviate this, but now the compiler is complaining about the functor instance:

Illegal instance declaration for ‘Convertible (f a) (f b)’
  The coverage condition fails in class ‘Convertible’
    for functional dependency: ‘a -> b’
  Reason: lhs type ‘f a’ does not determine rhs type ‘f b’
  Using UndecidableInstances might help
In the instance declaration for ‘Convertible (f a) (f b)’

Any thoughts about how to get this working? Or perhaps a better design if necessary? I'm thinking I may just have to settle for being explicit about which path of conversions to take.

While it's not likely to help you do what you're trying to do, you should definitely read Breitner, et al, Safe Zero-cost Coercions for Haskell. — dfeuer

chi chi · Accepted Answer · 2015-12-16T17:57:41

I think this has to require UndecidableInstances:

instance (Convertible a b, Convertible b c) => Convertible a c where

Given a, thanks to the functional dependency, we can compute a b. However, there's no guarantee that such b is smaller/simpler than a! It could be e.g. that b ~ [[a]], in which case we reduce the problem of checking Convertible a c to checking Convertible [[a]] c. This can easily lead to non-termination during instance search, since the class arguments are not decreasing.

Related note: if you satisfy the functional dependency, there is only one type b to which you can convert a. In such case, why do you need transitivity? There's nothing else a can be converted to. In other words, in the transitivity case you need to have c ~ b, or you would have that a determines both b and c, violating the functional dependency. (I guess you do not really want the functional dependency, after all.)

Unrelated note: also watch out for instance overlaps -- the instance above looks quite troublesome. You might also have to use OverlappingInstances and/or IncoherentInstances, both of which can cause headaches.

Multiparameter typeclasses and illegal instance declarations

1 Answers