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! ^_^
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.