Почему тип идентификатора не может быть специализированным для (для a. A -> a) -> (для b. B -> b)?

Question

Возьмите скромную идентификационную функцию в 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 не имеет значения.

Answer 1

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

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

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

Answer 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)). В Системе 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) может быть примерно проиллюстрирован в Системе 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 это уже тип стрелки, и вызывающая сторона не может управлять созданием экземпляра. Это заставляет вызывающую сторону предоставить полиморфный аргумент.

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

Answer 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)

Здесь я приведу количественные переменные для ясности.

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

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

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

, что является просто сокращением для

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

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

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