Haskell - Типы перекрывающихся экземпляров и преобразования

Question

Я пишу код для реализации расширения по определениям в математических логиках c.

Он принимает описание языков и их расширений и выводит новое haskell файл, который будет анализировать язык высокого уровня на язык более низкого уровня. Конечно, если я могу превратить язык C в язык B, а язык B - в язык A, то с помощью сочинения я могу превратить C в A .... и все же ...

минимальный пример проблемы, с которой я сталкиваюсь:

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

Интуитивно понятно, что с instance (ToB a) => ToA a все в порядке, но компилятору это не нравится. Код как есть, правильно компилируется, но после замены явного экземпляра ToA C на закомментированную версию я получаю следующую ошибку:

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
   |                     ^^^^^

Конечно, я не боюсь расширений языка, поэтому Я делаю, как мне говорят, и добавляю FlexibleInstances, хотя я не думаю, что это должно помочь здесь. После этого мне сказали попробовать UndecidableInstances ... И на этом путь останавливается. Я все еще получаю ошибку типа, но я не уверен, что с этим делать.

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
   |                ^^^^^^^^^^

Это сообщение об ошибке особенно сбивает меня с толку, поскольку у меня есть только одно определение для ToA B. Эта ошибка имеет больше смысла, если бы B сам был экземпляром ToB, скажем, установив convertToB = id. Конечно, это не тот случай ...

Как мне правильно решить эту проблему? Заранее спасибо! ^ _ ^

Answer 1

Вы делаете правильные вещи. И вы правы, когда будете осторожны с Overlapping instances предупреждениями. В этом случае это связно. И вы не боитесь языковых расширений, поэтому вы хотите:

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

Эта вещь в {-# #-} - это прагма, которая представляет собой точный способ вызова языкового расширения только для этого экземпляра. , OVERLAPPABLE означает, что допускается наличие более конкретного c экземпляра (ToA B), и выберите его по предпочтению.

Ваше ограничение (ToB a) => действительно Undecidable, поскольку оно не меньше, чем Глава инстанции. UndecidableInstances является относительно «безопасным» расширением по сравнению с перекрытиями.

С перекрытиями небезопасными являются INCOHERENT (как бы плохо это не звучало) или «Сиротские экземпляры» - которые дают вам предупреждение компилятора иногда; здесь не применяется, потому что все ваши экземпляры находятся в том же модуле, что и объявление класса.