Почему тип идентификатора не может быть специализированным для (для 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 в вашем типе фактически запрещает объединяться с любым другим типом.

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 над ОД. Вы также можете обратиться к главам 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) - это невозможно в оперативном отношении, даже если ваш тип позволит им.