Can I automatically produce typeclass instances for a conversion function without being overly permissive?

Question

Recently, I asked a question about an instance I had created generating a runtime infinite loop, and I got a wonderful answer! Now that I understand what was going on, I have a new question: can I fix my attempt to accomplish my original goal?

Let me reiterate and clarify specifically what my problem is: I want to create a typeclass that is used to convert between some equivalent datatypes in my code. The typeclass I created is both very simple and very general: it includes a single conversion function that converts between arbitrary datatypes:

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

However, this typeclass has a specific purpose: converting between a specific class of values, which have a canonical representation. Therefore, there is a specific datatype which is “canonical”, and I want to use the property of this datatype to reduce the burden on implementors of my typeclass.

data Canonical = ...

class ConvertRep a b where
  convertRep :: a -> b

Specifically, consider two different representations, RepA and RepB. I might reasonably define some instances to convert those representations to and from Canonical:

instance ConvertRep RepA Canonical where ...
instance ConvertRep Canonical RepA where ...

instance ConvertRep RepB Canonical where ...
instance ConvertRep Canonical RepB where ...

Now, this is immediately useful because I can now use convertRep for both kinds of representations, but it’s mostly just serving as a way to overload the convertRep name. I want to do something more powerful: after all, I have now effectively defined four functions with the following types:

RepA      -> Canonical
Canonical -> RepA
RepB      -> Canonical
Canonical -> RepB

It seems reasonable to me that, given these definitions, I should also be able to produce two functions of the following types:

RepA -> RepB
RepB -> RepA

Basically, since both datatypes can be converted to/from the canonical representation, I want to automatically produce a conversion function to/from each other directly. My attempt, as mentioned in my aforementioned question, looked like this:

instance (ConvertRep a Canonical, ConvertRep Canonical b) => ConvertRep a b where
  convertRep = convertRep . (convertRep :: a -> Canonical)

Unfortunately, this instance is far too permissive, and it causes the generated code to recurse when provided two types I think should be invalid—types I have not defined canonical conversions on yet.

---

To try and solve this problem, I considered another, simpler approach. I figured I could use two typeclasses instead of just one to prevent this recursion problem:

class ToCanonical a where
  toCanonical :: a -> Canonical

class FromCanonical a where
  fromCanonical :: Canonical -> a

Now it’s possible to define a new function that performs the convertRep conversion I was originally interested in:

convertRep :: (ToCanonical a, FromCanonical b) => a -> b
convertRep = fromCanonical . toCanonical

However, this comes at a cost of flexibility: it is no longer possible to create a direct conversion instance between two non-canonical representations.

For example, perhaps I know that RepA and RepB will be very frequently used interchangeably, and therefore they will be converted between each other quite a lot. Therefore, the extra step of converting to/from Canonical is wasted time. I would like to optionally define a direct conversion instance:

instance ConvertRep RepA RepB where
  convertRep = ...

which provides a “fast path” conversion between two common types.

---

To summarize: is there any way to accomplish all of these goals using Haskell’s type system?

1. “Generate” conversions between representations given functions that convert between the representations and a canonical form.
2. Optionally provide “fast paths” between instances that are commonly converted.
3. Reject instances that have not been explicitly defined; that is, do not permit ConvertRep Canonical Canonical (and similar) instances from being created that infinitely recur and produce bottom.

The Haskell type system is very impressive, but I worry that in this case its instance resolution rules are not powerful enough to accomplish all these goals at once.

Answer 1

OverlappingInstances can be used for fall-back behavior:

data A = A deriving (Show)
data B = B deriving (Show)
data C = C deriving (Show) -- canonical

class Canonical a where
  toC   :: a -> C
  fromC :: C -> a

class Conv a b where
  to   :: a -> b
  from :: b -> a

instance (Canonical a, Canonical b) => Conv a b where
  to   = fromC . toC
  from = fromC . toC

instance {-# overlapping #-} Conv A B where
  to   _ = B
  from _ = A

instance Canonical A where
  toC _ = C
  fromC _ = A

instance Canonical B where
  toC _ = C
  fromC _ = B

Conv converts directly if a direct instance exists or else falls back to conversion via C. The overlapping pragma signals that we wish to override the default instance. Alternatively, we could have put an overlappable pragma on the default instance, but that's more dangerous, since that would let all other instances - possibly defined in external modules - to be able to silently override.

However, I don't think this conversion scheme is particularly useful or good practice. Overlapping instances introduce the risk of different instances being resolved in different modules, and they can end up in the same module via imports and existential instances, possibly creating trouble.

Answer 2

You could use DefaultSignatures to specify the default implementation. While this still forces you to list all valid conversions manually it's relatively compact since you can rely on the default implementation. I.e. something like

{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE ScopedTypeVariables #-}

data Canonical = C

class ConvertRep a b where
  convertRep :: a -> b
  default convertRep :: (ConvertRep a Canonical, ConvertRep Canonical b) => a -> b
  convertRep = convertRep . (convertRep :: a -> Canonical)

data A = A
data B = B

instance ConvertRep A Canonical where
  convertRep A = C

instance ConvertRep Canonical B where
  convertRep C = B

Now you can define a conversion between A and B with just

instance ConvertRep A B

but it's still possible to overwrite the default implementation on a per-type basis.