Можно ли избежать UndecidableInstances в этом примере?

Question

Я пытаюсь реализовать двоичное дерево как класс типов:

      class BinaryTree bt where
    empty :: bt a -> Bool
    empty = isNothing . root
    emptyTree :: bt a
    branch :: a -> bt a -> bt a -> bt a 
    root :: bt a -> Maybe a
    lbranch :: bt a -> bt a 
    rbranch :: bt a -> bt a 

И я хочу проиллюстрировать, что двоичные деревья являются контейнерами данных, используя это определение:

      instance BinaryTree bt => Functor bt where
    fmap f bt = case root bt of
        Nothing -> emptyTree
        Just a -> branch (f a) (f <$> lbranch bt) (f <$> rbranch bt)

У меня есть:

      BinaryTree/BinaryTree.hs:18:10: error:
    • The constraint ‘BinaryTree bt’
        is no smaller than the instance head ‘Functor bt’
      (Use UndecidableInstances to permit this)
    • In the instance declaration for ‘Functor bt’

Использование абсолютно заставляет код компилироваться. Но мне интересно, правильно ли это использовать? Я читал о таких статьях, как «Когда UndecidableInstances безопасен?», но я не совсем понял.

---

Обновление 1: О том, «Зачем использовать классы типов»

Это часть исследования, в котором я пытаюсь правильно отличить полные бинарные деревья и совершенные бинарные деревья от обычных бинарных деревьев с помощью кода Haskell, описывая их свойства в коде Haskell. (Свойства: 1) полные двоичные деревья взаимно однозначно соответствуют спискам,идоступны, и 2) идеальные бинарные деревья представляют собой комбинацию двух идеальных бинарных деревьев одинаковой глубины. )

В частности, конечная цель — объявить тип полных двоичных деревьев, который при компиляции отклоняет значение, которое является двоичным деревом, но не полным двоичным деревом. (А также для идеальных бинарных деревьев.)

Исследования по-прежнему не прекращаются, и предложения приветствуются. Большое спасибо!

Answer 1

В неразрешимых случаях

это в основном безобидное расширение. Не волнуйтесь, если вам придется его включить.

В худшем случаеможет привести к зависанию компилятора в бесконечном цикле, если у вас есть взаимозависимые экземпляры, например

      instance A t => B t where ...
instance B t => A t where ...

Если вы будете стараться избегать этого, компилятор будет работать нормально.

Расширение не оказывает вредного воздействия на скомпилированный код, а только на саму компиляцию. Если ваш код компилируется, вы в безопасности.

О перекрывающихся экземплярах

С другой стороны, это повод для беспокойства.

      instance BinaryTree bt => Functor bt where

Руководитель этой инстанциии это пересекается с любыми другими примерами для. Этого следует избегать.

Разрешение экземпляра Haskell вообще не выполняет возврат назад , поскольку это может привести к экспоненциальному увеличению времени компиляции и поломке отдельной компиляции. Нет разумного способа написать что-то вроде

      instance MyClass1 f => Functor f where ...
instance MyClass2 f => Functor f where ...

Чтобы это работало, при разрешении Haskell должен сначала попытаться разрешить , и если это не удастся, попробуйте. На практике это оказывается слишком проблематично.

Обратите внимание, что Haskell позволяет объявлять экземпляры в любом модуле. Итак, чтобы проверить «нет экземпляра для«Haskell потребуется прочитать все модули в вашей программе. Это помешает компилятору скомпилировать модуль за раз, поэтому это запрещено.

Итак, экземпляр типа

      instance MyClass1 f => Functor f where ...

на самом деле означает «Если вы решаете, Вы должны иметь. Если вы этого не сделаете, потерпите неудачу». Это не импликация, а больше похоже на «тогда и только если». Компилятор фиксирует первый экземпляр, голова которого (часть) совпадает. Контекст экземпляра (часть) не учитывается до тех пор, пока компилятор не зафиксирует.

Есть несколько способов ослабить ограничения на перекрывающиеся экземпляры, но я не рекомендую их. Они очень хрупкие, если точно не понимать, что происходит под капотом.

Заключение

Чтобы избежать дублирования, вы можете использовать оболочку newtype:

      newtype F f a = F (f a)
instance BinaryTree bt => Functor (F bt) where

Даже если это не эквивалентно, вы можете указать суперкласс функтора:

      class Functor bt => BinaryTree bt where ...

Это заставит новые экземпляры гарантировать, что деревья являются функторами.

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