Ограничение класса типов Haskell не может быть разрешено из-за условий Патерсона

Question

Я пытаюсь построить AST с индексированными вложенными аннотациями. Я добавил класс типов для очистки аннотации на верхнем уровне и попытался предоставить экземпляры по умолчанию, которые фактически говорят: "Если вы знаете, как очищать аннотацию самостоятельно, то вы знаете, как очищать аннотацию на конкретном узле AST".

Так как один из моих узлов дерева является Nat Индексированный Predicate и его родительский элемент количественно определяют эту переменную, когда я пытаюсь написать экземпляр для родительского элемента, я застреваю в условиях Патерсона. А именно, у меня в утверждении больше переменных типа, чем в голове.

Если я включу UndecidableInstancesто GHC не может объединить переменные с видом Nat,

Если я дальше включу AllowAmbiguousTypesЗатем я получаю более абсурдную ошибку, в которой говорится, что не может найти экземпляр, несмотря на тот факт, что искомый экземпляр находится в утверждении экземпляра типа.

Мои вопросы:

1. Это на самом деле плохой экземпляр для написания, или проверка типов слишком консервативна?
2. Если это плохо или нет способа обойти проблему, как еще я могу обеспечить такое поведение очистки по умолчанию?

Вот минимальный код (я удалил биты, несущественные для ошибки типа, поэтому некоторые биты могут показаться избыточными):

{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE ExistentialQuantification #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE AllowAmbiguousTypes #-}

module Constraint where

data AnnType = ABase

data family PredicateAnn (a :: AnnType)
data instance PredicateAnn (a :: AnnType) = PABase

data Nat = Zero | Succ Nat

data Predicate (n :: Nat) (a :: AnnType) = Predicate
data Literal   (a :: AnnType) = forall n. Literal (Predicate n a)

class PeelableAST (ast :: AnnType -> *) (ann :: AnnType -> AnnType) where
  peel :: ast (ann a) -> ast a

class PeelableAnn (f :: AnnType -> *) (ann :: AnnType -> AnnType) where
  peelA :: f (ann a) -> f a

instance PeelableAST (Predicate n) ann
         => PeelableAST Literal ann where
  peel (Literal predicate) = Literal (peel predicate)

instance PeelableAnn PredicateAnn ann => PeelableAST (Predicate n) ann where
  peel Predicate = Predicate

Вот точная ошибка без UndecidableInstances:

src/Constraint.hs:27:10: error:
• Variable ‘n’ occurs more often
    in the constraint ‘PeelableAST (Predicate n) ann’
    than in the instance head
  (Use UndecidableInstances to permit this)
• In the instance declaration for ‘PeelableAST Literal ann’
   |
27 | instance PeelableAST (Predicate n) ann
   |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

И вот с этим:

src/Constraint.hs:28:10: error:
• Could not deduce (PeelableAST (Predicate n0) ann)
  from the context: PeelableAST (Predicate n) ann
    bound by an instance declaration:
               forall (n :: Nat) (ann :: AnnType -> AnnType).
               PeelableAST (Predicate n) ann =>
               PeelableAST Literal ann
    at src/Constraint.hs:(28,10)-(29,35)
  The type variable ‘n0’ is ambiguous
• In the ambiguity check for an instance declaration
  To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
  In the instance declaration for ‘PeelableAST Literal ann’
   |
28 | instance PeelableAST (Predicate n) ann
   |          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^...

Вот тот, с AllowAmbiguousTypes:

 src/Constraint.hs:31:39: error:
• Could not deduce (PeelableAnn PredicateAnn ann)
    arising from a use of ‘peel’
  from the context: PeelableAST (Predicate n) ann
    bound by the instance declaration
    at src/Constraint.hs:(29,10)-(30,35)
• In the first argument of ‘Literal’, namely ‘(peel predicate)’
  In the expression: Literal (peel predicate)
  In an equation for ‘peel’:
      peel (Literal predicate) = Literal (peel predicate)
   |
31 |   peel (Literal predicate) = Literal (peel predicate)
   |                                       ^^^^^^^^^^^^^^

РЕДАКТИРОВАТЬ:

Поскольку Даниэль Вагнер предлагает одно решение, чтобы сделать PeelableAnn PredicateAnn ann утверждение в PeelableAST Literal ann пример. Тем не менее, я никогда не использую peelA определяется PeelableAnn в PeelableAST Literal ann определение, и я хотел бы, чтобы этот экземпляр вел себя как поведение по умолчанию и мог перезаписать его, непосредственно предоставив PeelableAST (Predicate n) ann пример. Другими словами, пилинг может быть по сути контекстным.

поскольку PeelableAnn PredicateAnn ann требуется PeelableAST (Predicate n) annЯ чувствую, что GHC должен быть в состоянии найти и удовлетворить это условие.

Я могу просто подделать PeelableAnn PredicateAnn ann экземпляр должен быть проигнорирован более конкретным, но это довольно хакерский

Answer 1

В вашем PeelableAST Literal ann Например, вы используете PeelableAST (Predicate n) ann пример. Если средство проверки типов хочет использовать этот экземпляр, оно должно проверить свое предварительное условие, а именно, что PeelableAnn PredicateAnn ann держит. Но он этого не знает, потому что вы не сделали это предварительным условием вашего PeelableAST Literal ann пример.

Это нормально; это легко исправить и позволяет полностью избежать неоднозначного типа. Просто добавьте предварительное условие, о котором вы беспокоитесь, как предварительное условие для вас PeelableAST Literal ann пример. Действительно, так как теперь это является предварительным условием для обоих случаев, вы можете также отбросить PeelableAnn PredicateAnn ann предварительное условие, как это следует из этого нового и более сильного условия. Так:

instance PeelableAnn PredicateAnn ann => PeelableAST Literal ann where
    peel (Literal predicate) = Literal (peel predicate)

Вы можете удалить AllowAmbiguousTypes, хоть UndecidableInstances все еще нужно, потому что PeelableAnn PredicateAnn ann не очевидно, конструктивно меньше, чем PeelableAST Literal ann,