GHC завис из-за UndecidableSuperClasses - ожидаемое поведение или ошибка?

Question

Следующий фрагмент кода приводит к зависанию GHC (проверено с помощью 8.6.2 и 8.4.4) во время компиляции:

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE UndecidableSuperClasses #-}

import GHC.Exts (Constraint)

data T = T

type family F t (c :: * -> Constraint) :: Constraint
type instance F T c = c T

class F t C => C t where

t :: C T => t
t = undefined

Я думаю, что это застревает, потому что для t GHC пытается найти C T, что приводит к F T C который расширяется за счет семейства типов F вернуться к C T, что он и искал (бесконечный цикл).

Я полагаю, что теоретически GHC мог бы сказать, что достиг своего C T от самого себя и что все, что зависит от него самого, может нормально работать рекурсивно, или я что-то неправильно понимаю?

Примечание: в реальном примере, где я наткнулся на это поведение, я смог достичь того, чего хотел без компилятора, заменив его UndecidableSuperClasses с Data.Constraint.Dict вместо.

Answer 1

UndecidableSuperClasses не делает разрешение экземпляра ленивым. Компилятор по-прежнему будет расширять ограничения суперкласса, насколько это возможно. Я считаю, что поля в словарях экземпляров, которые указывают на словари суперкласса, являются строгими, и GHC фактически связывает их во время компиляции. Это в отличие от UndecidableInstances, что позволяет обрабатывать ограничения экземпляра (немного) лениво.

deriving instance Show (f (Fix f)) => Show (Fix f)

будет работать просто отлично. При разрешении экземпляра, например, для Show (Fix Maybe)), GHC увидит, что ему нужно Show (Maybe (Fix Maybe)), Затем он видит, что нужно Show (Fix Maybe) (который в настоящее время решается) и принять это благодаря UndecidableInstances,

Все UndecidableSuperClases действительно отключает проверки, которые гарантируют, что расширение не будет зациклено. Посмотрите немного в начале выступления Эда Кметта, где он описывает процесс "достижения фиксированной точки".

Рассмотрим рабочий пример Data.Constraint.Forall):

type family Skolem (p :: k -> Constraint) :: k
class p (Skolem p) => Forall (p :: k -> Constraint)

GHC принимает это только с UndecidableSuperclasses, Зачем? Потому что он ничего не знает о том, что может означать это ограничение. Насколько он знает, это может быть так, что p (Skolem p) уменьшится до Forall p, И это действительно может произойти!

class Forall P => P x

-- This definition loops the type checker
foo :: P x => x
foo = undefined