CODEWITHSUNDEEP
haskelltypestypeclassoverlapping-instances
Chris Grossack
Chris Grossack

Reputation: 103

Haskell - Overlapping Instances and Conversion typeclass

I'm writing code to implement extension by definitions in mathematical logic.

It takes in a description of languages and their extensions, and it outputs a new haskell file which will parse a high-level language into a lower-level one. Of course, if I can turn language C into language B, and language B into language A, then by composing I can turn C to A.... and yet...

Here is a minimal example of the problem I'm facing:

data A = EmptyA | NodeA A A
data B = EmptyB | NodeB B B | UnaryB B
data C = EmptyC | NodeC C C | UnaryC C | TernaryC C C C


class ToA a where
  convertToA :: a -> A

class ToB a where
  convertToB :: a -> B


instance ToA B where
  convertToA EmptyB      = EmptyA
  convertToA (NodeB l r) = NodeA (convertToA l) (convertToA r)
  convertToA (UnaryB l)  = NodeA (convertToA l) EmptyA

instance ToB C where
  convertToB EmptyC           = EmptyB
  convertToB (NodeC l r)      = NodeB (convertToB l) (convertToB r)
  convertToB (UnaryC l)       = UnaryB (convertToB l)
  convertToB (TernaryC l m r) = NodeB (convertToB l) (NodeB (convertToB m) (convertToB r))


-- instance (ToB a) => ToA a where
--   convertToA = convertToA . convertToB

-- I shouldn't have to write this
instance ToA C where
  convertToA  = convertToA . convertToB

Intuitively, there's nothing wrong with instance (ToB a) => ToA a, but the compiler doesn't like it. The code as is, compiles properly, but upon replacing the explicit ToA C instance with the commented version, I receive the following error:


minimal.hs:25:21: error:
    • Illegal instance declaration for ‘ToA a’
        (All instance types must be of the form (T a1 ... an)
         where a1 ... an are *distinct type variables*,
         and each type variable appears at most once in the instance head.
         Use FlexibleInstances if you want to disable this.)
    • In the instance declaration for ‘ToA a’
   |
25 | instance (ToB a) => ToA a where
   |                     ^^^^^

Of course, I'm not afraid of language extensions, so I do as I'm told and add FlexibleInstances, even though I don't think it should help here. After doing this, I'm told to try UndecidableInstances... And that's where the trail stops. I'm still getting a type error, but I'm not sure what to do about it.

minimal.hs:29:16: error:
    • Overlapping instances for ToA B
        arising from a use of ‘convertToA’
      Matching instances:
        instance ToB a => ToA a -- Defined at minimal.hs:28:10
        instance ToA B -- Defined at minimal.hs:16:10
    • In the first argument of ‘(.)’, namely ‘convertToA’
      In the expression: convertToA . convertToB
      In an equation for ‘convertToA’:
          convertToA = convertToA . convertToB
   |
29 |   convertToA = convertToA . convertToB
   |                ^^^^^^^^^^

This error message is especially confusing to me, since I only have one definition for ToA B. This error would make more sense if B was itself an instance of ToB, say by setting convertToB = id. Of course, that's not the case here...

How am I supposed to properly handle this issue? Thanks in advance! ^_^

Upvotes: 0

Views: 178

Answers (1)

AntC
AntC

Reputation: 2806

You're doing the right things. And you're right to be cautious about Overlapping instances warnings. In this case it is coherent. And you're not afraid of language extensions, so you want:

instance {-# OVERLAPPABLE #-} (ToB a) => ToA a where
  convertToA = convertToA . convertToB

That thing in {-# #-} is a pragma, which is a closely-tailored way to invoke a language extension, for just this instance. OVERLAPPABLE means allow there to be a more specific instance (ToA B), and choose that by preference.

Your constraint (ToB a) => is indeed Undecidable because it is no smaller than the instance head. UndecidableInstances is a relatively 'safe' extension compared to overlaps.

With overlaps the unsafe uses are INCOHERENT (just as bad as it sounds) or 'Orphan instances' -- which give you a compiler warning sometimes; doesn't apply here because all your instances are in the same module as the class declaration.

Upvotes: 3

Related Questions