Я понимаю, как forall позволяет нам писать полиморфную функцию.
В соответствии с этой главой нормальная функция, которую мы обычно пишем, это типы 1-го уровня. И эта функция имеет тип 2-го уровня:
foo :: (forall a. a -> a) -> (Char,Bool)
foo f = (f 'c', f True)
Это объясняется следующим образом:
В общем случае тип rank-n является функцией, которая имеет хотя бы одну rank-(n-1), но нет аргументов еще более высокого ранга.
Что это значит для аргументов ранга?
Может ли кто-нибудь привести пример типа 3-го уровня, который аналогичен предыдущей функции foo.
Ранг определяется индуктивно по структуре типов:
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
и т.д.
n - это уровень, на котором forall (s) является/вложенным. Итак, если у вас есть forall a. ((a -> a) -> Bla) (это просто более подробный способ записи (a -> a) -> Bla), то forall находится снаружи и применяется ко всей функции, поэтому он занимает ранг 1. С помощью (forall a. a -> a) -> Bla forall применяется только к внутренней функции (т.е. той, которую вы принимаете в качестве аргумента) и, таким образом, занимает 2-е место.
Если функция, которую вы принимаете в качестве аргумента, сама возьмет другую функцию в качестве аргумента, и эта функция будет иметь forall в своем типе, тогда это будет ранг 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.