Что такое "n" в RankNTypes

Я понимаю, как forall позволяет нам писать полиморфную функцию.

В соответствии с этой главой нормальная функция, которую мы обычно пишем, это типы 1-го уровня. И эта функция имеет тип 2-го уровня:

foo :: (forall a. a -> a) -> (Char,Bool)
foo f = (f 'c', f True)

Это объясняется следующим образом:

В общем случае тип rank-n является функцией, которая имеет хотя бы одну rank-(n-1), но нет аргументов еще более высокого ранга.

Что это значит для аргументов ранга?

Может ли кто-нибудь привести пример типа 3-го уровня, который аналогичен предыдущей функции foo.

Ответ 1

Ранг определяется индуктивно по структуре типов:

rank (forall a. T) = max 1 (rank T)
rank (T -> U)      = max (if rank T = 0 then 0 else rank T + 1) (rank U)
rank (a)           = 0

Обратите внимание, как он увеличивается на единицу в левой части стрелки. Итак:

Rank 0: Int
Rank 1: forall a. a -> Int
Rank 2: (forall a. a -> Int) -> Int
Rank 3: ((forall a. a -> Int) -> Int) -> Int

и т.д.

Ответ 2

n - это уровень, на котором forall (s) является/вложенным. Итак, если у вас есть forall a. ((a -> a) -> Bla) (это просто более подробный способ записи (a -> a) -> Bla), то forall находится снаружи и применяется ко всей функции, поэтому он занимает ранг 1. С помощью (forall a. a -> a) -> Bla forall применяется только к внутренней функции (т.е. той, которую вы принимаете в качестве аргумента) и, таким образом, занимает 2-е место.

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

Ответ 3

foo имеет один аргумент, который включает универсальный квантор, что то, что пинает необходимость в RankN. Но этот тип аргумента сам по себе, a -> a, является ранг-1, это единственный аргумент, поэтому foo имеет ранг n с n-1 = 1, т.е. foo является ранга-2.

Теперь рассмотрим

bar :: ((forall a. a -> a) -> (Char,Bool)) -> Int

У этого есть аргумент типа foo, который, как мы сказали, имеет Ранг 2. Таким образом, самый высокий ранг в аргументах bar; bar является, таким образом, функцией ранга 3.