Что такое skolems?

Ответ 1

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

Это очень похоже на переменные, связанные с лямбдой: учитывая лямбда (\x -> ... ), из "снаружи" вы можете применить его к любой ценности, которая вам нравится, конечно; но внутри, вы не можете просто решить, что значение x должно быть определенным значением. Выбор значения для x внутри лямбда должен звучать довольно глупо, но то, что означает ошибки "не могут совпадать с бла-бла, жесткой переменной типа, бла-бла".

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

Конечно, это не ошибка, которую вы получаете. То, что означает "экранированная переменная типа", является еще более глупым - ему нравится иметь лямбда (\x -> ...) и пытается использовать определенные значения x вне лямбда, независимо от применения его к аргументу. Нет, не применяя лямбда к чему-либо и используя значение результата - я имею в виду фактически использование самой переменной вне области, в которой она определена.

Причина, по которой это может происходить с типами (без кажущегося абсурдного, как пример с лямбдой), состоит в том, что существуют два понятия "переменные типа", плавающие вокруг: во время унификации у вас есть "переменные", представляющие неопределенные типы, которые затем идентифицируются с другими такими переменными посредством вывода типа. С другой стороны, у вас есть квантифицированные переменные типа, описанные выше, которые конкретно идентифицируются как ранжирование по возможным типам.

Рассмотрим тип лямбда-выражения (\x -> x). Начиная с совершенно неопределенного типа a, мы видим, что он принимает один аргумент и сужает его до a -> b, тогда мы видим, что он должен возвращать что-то типа того же типа, что и его аргумент, поэтому мы ограничиваем его до a -> a. Но теперь он работает для любого типа a, который вам может понадобиться, поэтому мы даем ему квантификатор (forall a. a -> a).

Итак, переменная типа escaped возникает, когда у вас есть привязка типа квантификатором, который GHC-infers должен быть унифицирован с неопределенным типом вне области действия этого квантификатора.

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

Я не совсем уверен, откуда взялся этот термин, но я бы предположил, что он включает нормальную форму Сколема и представляет экзистенциальную количественную оценку с точки зрения универсальности, как это делается в GHC. Переменная типа сколема (или жесткого типа) является той, которая по какой-то причине имеет неизвестный, но специфический тип по какой-либо причине, являясь частью полиморфного типа, исходящего из экзистенциального типа данных, & c.

Ответ 2

Как я понимаю, "переменная Skolem" - это переменная, которая не соответствует какой-либо другой переменной, включая ее.

Это, кажется, появляется в Haskell, когда вы используете такие функции, как явные форварды, GADT и другие расширения системы.

Например, рассмотрим следующий тип:

data AnyWidget = forall x. Widget x => AnyWidget x

В этом говорится, что вы можете использовать любой тип, который реализует класс Widget, и переносить его в тип AnyWidget. Теперь предположим, что вы пытаетесь развернуть это:

unwrap (AnyWidget w) = w

Ум, нет, ты не можешь этого сделать. Потому что во время компиляции мы понятия не имеем, что такое тип w, поэтому нет способа написать правильную сигнатуру типа для этого. Здесь тип w "экранировался" из AnyWidget, что недопустимо.

Как я понимаю, внутренне GHC дает w тип, который является переменной Skolem, чтобы представить тот факт, что он не должен убегать. (Это не единственный такой сценарий: там есть несколько других мест, где определенное значение не может выйти из-за проблем с вводом текста.)

Ответ 3

Сообщение об ошибке появляется, когда переменная типа пытается избежать ее области.

Мне потребовалось некоторое время, чтобы понять это, поэтому я напишу пример.

{-# LANGUAGE ExistentialQuantification #-}
data I a = I a deriving (Show)
data SomeI = forall a. MkSomeI (I a)

Тогда, если мы попытаемся написать функцию

 unI (MkSomeI i) = i

GHC отказывается от ввода-вывода/проверки подлинности этой функции.

Почему? Попробуем сделать вывод о самом типе:

• unI - это определение лямбда, поэтому для некоторых типов x и y это тип x -> y.
• MkSomeI имеет тип forall a. I a -> SomeI
  • MkSomeI i имеет тип SomeI
  • i на LHS имеет тип I z для некоторого типа z. Из-за квантора forall нам пришлось ввести новую (новую) переменную типа. Обратите внимание, что он не универсален, поскольку он связан внутри выражения (SomeI i).
  • Таким образом, мы можем объединить переменную типа x с SomeI, это нормально. Таким образом, unI должен иметь тип SomeI -> y.
• i на RHS имеют тип I z.
• В этот момент унификатор пытается объединить y и I z, но он замечает, что z вводится в нижнем контексте. Таким образом, он терпит неудачу.

В противном случае тип для unI будет иметь тип forall z. SomeI -> I z, но правильный - exists z. SomeI -> I z. Тем не менее, один GHC не может представлять напрямую.

Аналогично, мы можем видеть, почему

data AnyEq = forall a. Eq a => AE a
-- reflexive :: AnyEq -> Bool
reflexive (AE x) = x == x

работы.

(экзистенциальная) переменная внутри AE x не выходит во внешнюю область, поэтому все в порядке.

Также я столкнулся с "feature" в GHC 7.8.4 и 7.10.1, где RankNTypes сам по себе в порядке, но добавление GADTs вызывает ошибку

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE GADTs #-}

example :: String -> I a -> String
example str x = withContext x s
  where
    s i = "Foo" ++ str

withContext :: I a -> (forall b. I b -> c) -> c
withContext x f = f x

Таким образом, это может быть неправильно с вашим кодом. Это может быть GHC, который не может понять все последовательно.

EDIT: решение должно дать тип s :: forall a. I a -> String.

GADTs включить MonoLocalBinds, что делает предполагаемый тип s для переменной skolem, поэтому тип не forall a. I a -> String, но t -> String, были t связаны в неправильном контексте. См.: https://ghc.haskell.org/trac/ghc/ticket/10644