Почему не может быть специфицирован тип id (forall a. A → a) → (forall b. B → b)?

Возьмите скромную функцию идентификации в Haskell,

id :: forall a. a -> a

Учитывая, что Haskell предположительно поддерживает недискриминационный полиморфизм, представляется разумным, что я должен "ограничивать" id типом (forall a. a -> a) -> (forall b. b -> b) по типу типа. Но это не работает:

Prelude> id :: (forall a. a -> a) -> (forall b. b -> b)

<interactive>:1:1:
    Couldn't match expected type `b -> b'
                with actual type `forall a. a -> a'
    Expected type: (forall a. a -> a) -> b -> b
      Actual type: (forall a. a -> a) -> forall a. a -> a
    In the expression: id :: (forall a. a -> a) -> (forall b. b -> b)
    In an equation for `it':
        it = id :: (forall a. a -> a) -> (forall b. b -> b)

Конечно, можно определить новую ограниченную форму тождественной функции с нужной сигнатурой:

restrictedId :: (forall a. a -> a) -> (forall b. b -> b)
restrictedId x = x

Однако определение его в терминах общего id не работает:

restrictedId :: (forall a. a -> a) -> (forall b. b -> b)
restrictedId = id -- Similar error to above

Итак, что здесь происходит? Похоже, что это может быть связано с трудностями с непроницаемостью, но включение -XImpredicativeTypes не имеет значения.

Ответ 1

почему он ожидает тип (forall a. a -> a) -> b -> b

Я думаю, что тип forall b.(forall a. a -> a) -> b -> b эквивалентен типу, который вы дали. Это просто каноническое представление его, где forall сдвигается как можно дальше влево.

И причина, по которой он не работает, заключается в том, что данный тип на самом деле более полиморфен, чем тип id:: forall c. c → c, что требует, чтобы аргументы и возвращаемые типы были равны. Но forall a в вашем типе эффективно запрещает объединять с любым другим типом.

Ответ 2

Вы абсолютно правы, что forall b. (forall a. a -> a) -> b -> b не эквивалентен (forall a. a -> a) -> (forall b. b -> b).

Если не указано иное, переменные типа определяются количественно на самом внешнем уровне. Итак, (a -> a) -> b -> b является сокращением для (forall a. (forall b. (a -> a) -> b -> b)). В System F, где абстракция и приложение типа явно выражены, это описывает термин типа f = Λa. Λb. λx:(a -> a). λy:b. x y. Чтобы быть понятным для тех, кто не знаком с обозначениями, Λ - это лямбда, которая принимает тип в качестве параметра, в отличие от λ, который принимает член как параметр.

Вызывающий f сначала предоставляет параметр типа a, затем поставляет параметр типа b, затем поставляет два значения x и y, которые придерживаются выбранных типов. Важно отметить, что вызывающий абонент выбирает a и b. Таким образом, вызывающий может выполнять приложение типа f String Int length, например, для создания термина String -> Int.

Используя -XRankNTypes, вы можете аннотировать термин, явно помещая универсальный квантификатор, он не должен находиться на самом внешнем уровне. Ваш термин restrictedId с типом (forall a. a -> a) -> (forall b. b -> b) может быть примерно проиллюстрирован в System F как g = λx:(forall a. a -> a). if (x Int 0, x Char 'd') > (0, 'e') then x else id. Обратите внимание, что g, вызываемый, может применять x как к 0, так и к 'e' путем создания экземпляра с первым типом.

Но в этом случае вызывающий не может выбрать параметр типа, как раньше, с помощью f. Вы заметите приложения x Int и x Char внутри лямбда. Это заставляет вызывающего обеспечить полиморфную функцию, поэтому термин, такой как g length, недействителен, поскольку length не применяется к Int или Char.

Другой способ подумать об этом - это рисовать типы f и g как дерево. Дерево для f имеет универсальный квантификатор в качестве корня, а дерево для g имеет стрелку в качестве корня. Чтобы перейти к стрелке в f, вызывающий объект создает два квантификатора. С g он уже является типом стрелки, и вызывающий не может управлять экземпляром. Это заставляет вызывающего пользователя предоставить полиморфный аргумент.

Наконец, пожалуйста, простите мои надуманные примеры. Габриэль Шерер описывает еще несколько практических применений полиморфизма более высокого ранга в Умеренно практическое использование System F over ML. Вы также можете ознакомиться с главами 23 и 30 из TAPL или просмотреть документацию для расширений компилятора, чтобы найти более подробные или более практичные примеры полиморфизма более высокого ранга.

Ответ 3

Я не эксперт по поводу непрогнозируемых типов, поэтому это сразу потенциальный ответ и попытка узнать что-то из комментариев.

Не имеет смысла специализироваться

\/ a . a -> a                       (1)

(\/ a . a -> a) -> (\/ b . b -> b)  (2)

и я не думаю, что причиной этого могут быть неискренние типы. Квантификаторы приводят к созданию типов, представленных левой и правой частью (2) неэквивалентных множеств вообще. Однако a -> a в (1) подразумевает, что левая и правая стороны являются эквивалентными множествами.

например. вы можете конкретизировать (2) - (int → int) → (string → string). Но любой системой я знаю, что это не тип, представленный (1).

Сообщение об ошибке выглядит так, будто это результат попытки инкрементного типа Haskel унифицировать тип id

\/ a . a -> a

с типом, который вы указали

\/ c . (c -> c) -> \/ d . (d -> d)

Здесь для ясности я унифицирую квантифицированные переменные.

Задача типа inferencer состоит в том, чтобы найти наиболее общее назначение для a, c и d, которое заставляет два выражения синтаксически равными. В конечном итоге он находит, что для объединения требуется c и d. Поскольку они отдельно оцениваются, они находятся в тупике и завершают работу.

Возможно, вы задаете вопрос, потому что базовый тип inferencer - с надписью (c -> c) -> (d -> d) - будет просто пахать вперед и установить c == d. Результирующий тип будет

(c -> c) -> (c -> c)

который является просто сокращенным для

\/c . (c -> c) -> (c -> c)

Это, по-видимому, наименее общий тип (тип теоретической наименее верхней границы) выражения для типа x = x, где x ограничивается функцией с тем же доменом и со-доменом.

Тип "restricedId", как указано, в реальном смысле чрезмерно общий. Хотя он никогда не может привести к ошибке типа времени выполнения, существует много типов, описанных выражением, которое вы ему дали - как и вышеупомянутое (int -> int) -> (string -> string) - которые невозможно оперативно, даже если ваш тип позволит им.