Какова цель Rank2Types?
Я не очень разбираюсь в Хаскеле, так что это может быть очень простой вопрос.
Какие языковые ограничения решает Rank2Types? Разве функции в Haskell уже не поддерживают полиморфные аргументы?
6 ответов
Разве функции в Haskell уже не поддерживают полиморфные аргументы?
Они делают, но только с рангом 1. Это означает, что хотя вы можете написать функцию, которая принимает разные типы аргументов без этого расширения, вы не можете написать функцию, которая использует свой аргумент как разные типы в одном и том же вызове.
Например, следующая функция не может быть набрана без этого расширения, потому что g используется с различными типами аргументов в определении f:
f g = g 1 + g "lala"
Обратите внимание, что вполне возможно передать полиморфную функцию в качестве аргумента другой функции. Так что-то вроде map id ["a","b","c"] совершенно законно. Но функция может использовать ее только как мономорфную. В примере map использования id как будто у него был тип String -> String, И, конечно, вы также можете передать простую мономорфную функцию данного типа вместо id, Без ранга2 нет возможности для функции требовать, чтобы ее аргумент был полиморфной функцией и, следовательно, также нельзя было использовать ее как полиморфную функцию.
Трудно понять полиморфизм более высокого ранга, если вы не изучите Систему F напрямую, потому что Haskell разработан, чтобы скрыть детали этого от вас в интересах простоты.
Но в принципе, грубая идея заключается в том, что полиморфные типы на самом деле не имеют a -> b форма, которую они делают в Хаскеле; на самом деле они выглядят так, всегда с явными квантификаторами:
id :: ∀a.a → a
id = Λt.λx:t.x
Если вы не знаете символ "∀", он читается как "для всех"; ∀x.dog(x) означает "для всех х, х собака". "Λ" - прописная лямбда, используемая для абстрагирования от параметров типа; во второй строке написано, что id - это функция, которая принимает тип t, а затем возвращает функцию, параметризованную этим типом.
Видите ли, в системе F вы не можете просто применить такую функцию id к стоимости сразу; сначала вам нужно применить Λ-функцию к типу, чтобы получить λ-функцию, которую вы применяете к значению. Так, например:
(Λt.λx:t.x) Int 5 = (λx:Int.x) 5
= 5
Стандартный Haskell (т. Е. Haskell 98 и 2010) упрощает это для вас, поскольку у вас нет ни одного из этих квантификаторов типов, прописных лямбда-выражений и приложений типов, но за кулисами GHC помещает их при анализе программы для компиляции. (Я полагаю, что все это во время компиляции без лишних затрат времени выполнения.)
Но автоматическая обработка Хаскеллом этого означает, что предполагается, что "∀" никогда не появляется в левой ветви типа функции ("→"). Rank2Types а также RankNTypes отключить эти ограничения и позволить вам переопределить правила по умолчанию Haskell для того, где вставить forall,
Зачем тебе это делать? Потому что полная, неограниченная System F очень мощная, и она может делать много интересных вещей. Например, скрытие типов и модульность могут быть реализованы с использованием типов более высокого ранга. Возьмем, к примеру, простую старую функцию следующего типа ранга 1 (для установки сцены):
f :: ∀r.∀a.((a → r) → a → r) → r
Использовать f вызывающий сначала должен выбрать, какие типы использовать r а также a, затем укажите аргумент полученного типа. Так что вы можете выбрать r = Int а также a = String:
f Int String :: ((String → Int) → String → Int) → Int
Но теперь сравните это со следующим типом более высокого ранга:
f' :: ∀r.(∀a.(a → r) → a → r) → r
Как работает функция этого типа? Ну, чтобы использовать его, сначала вы указываете, какой тип использовать для r, Скажем, мы выбираем Int:
f' Int :: (∀a.(a → Int) → a → Int) → Int
Но теперь ∀a находится внутри стрелки функции, поэтому вы не можете выбрать, какой тип использовать для a; вы должны подать заявку f' Int к Λ-функции соответствующего типа. Это означает, что реализация f' можно выбрать, какой тип использовать для a не вызывающий f', Напротив, без типов более высокого ранга вызывающий всегда выбирает типы.
Для чего это нужно? Ну, на самом деле, для многих вещей, но одна идея состоит в том, что вы можете использовать это для моделирования таких вещей, как объектно-ориентированное программирование, где "объекты" связывают некоторые скрытые данные вместе с некоторыми методами, которые работают со скрытыми данными. Так, например, объект с двумя методами - один, который возвращает Int и другой, который возвращает String, может быть реализовано с этим типом:
myObject :: ∀r.(∀a.(a → Int, a -> String) → a → r) → r
Как это работает? Объект реализован как функция, которая имеет некоторые внутренние данные скрытого типа. a, Чтобы фактически использовать объект, его клиенты передают функцию "обратного вызова", которую объект будет вызывать с помощью двух методов. Например:
myObject String (Λa. λ(length, name):(a → Int, a → String). λobjData:a. name objData)
Здесь мы, в основном, вызываем второй метод объекта, тот, чей тип a → String для неизвестного a, Ну неизвестно myObject клиенты; но эти клиенты знают из подписи, что они смогут применить к нему любую из двух функций и получить либо Int или String,
Для реального примера на Haskell ниже приведен код, который я написал, когда учил сам RankNTypes, Это реализует тип с именем ShowBox который связывает воедино значение некоторого скрытого типа вместе с его Show экземпляр класса. Обратите внимание, что в примере внизу я делаю список ShowBox чей первый элемент был сделан из числа, а второй из строки. Поскольку типы скрыты с использованием типов более высокого ранга, это не нарушает проверку типов.
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ImpredicativeTypes #-}
type ShowBox = forall b. (forall a. Show a => a -> b) -> b
mkShowBox :: Show a => a -> ShowBox
mkShowBox x = \k -> k x
-- | This is the key function for using a 'ShowBox'. You pass in
-- a function @k@ that will be applied to the contents of the
-- ShowBox. But you don't pick the type of @k@'s argument--the
-- ShowBox does. However, it's restricted to picking a type that
-- implements @Show@, so you know that whatever type it picks, you
-- can use the 'show' function.
runShowBox :: forall b. (forall a. Show a => a -> b) -> ShowBox -> b
-- Expanded type:
--
-- runShowBox
-- :: forall b. (forall a. Show a => a -> b)
-- -> (forall b. (forall a. Show a => a -> b) -> b)
-- -> b
--
runShowBox k box = box k
example :: [ShowBox]
-- example :: [ShowBox] expands to this:
--
-- example :: [forall b. (forall a. Show a => a -> b) -> b]
--
-- Without the annotation the compiler infers the following, which
-- breaks in the definition of 'result' below:
--
-- example :: forall b. [(forall a. Show a => a -> b) -> b]
--
example = [mkShowBox 5, mkShowBox "foo"]
result :: [String]
result = map (runShowBox show) example
PS: для тех, кто читает это, кто интересуется, как получилось ExistentialTypes в GHC использует forall Я считаю, что причина в том, что он использует такую технику за кулисами.
Ответ Луиса Касильяс дает много отличной информации о том, что означают типы ранга 2, но я просто остановлюсь на одном моменте, который он не охватил. Требование, чтобы аргумент был полиморфным, не только позволяет использовать его с несколькими типами; это также ограничивает то, что эта функция может делать со своими аргументами и как она может производить свой результат. То есть это дает вызывающему меньше гибкости. Почему вы хотите это сделать? Я начну с простого примера:
Предположим, у нас есть тип данных
data Country = BigEnemy | MediumEnemy | PunyEnemy | TradePartner | Ally | BestAlly
и мы хотим написать функцию
f g = launchMissilesAt $ g [BigEnemy, MediumEnemy, PunyEnemy]
который принимает функцию, которая должна выбрать один из элементов списка, который он дал, и вернуть IO действие запуска ракет на этой цели. Мы могли бы дать f простой тип:
f :: ([Country] -> Country) -> IO ()
Проблема в том, что мы могли случайно запустить
f (\_ -> BestAlly)
и тогда у нас будут большие неприятности! дающий f полиморфный тип 1 ранга
f :: ([a] -> a) -> IO ()
не помогает вообще, потому что мы выбираем тип a когда мы звоним fи мы просто специализируемся на Country и использовать наши вредоносные \_ -> BestAlly снова. Решение состоит в том, чтобы использовать тип ранга 2:
f :: (forall a . [a] -> a) -> IO ()
Теперь функция, которую мы передаем, должна быть полиморфной, поэтому \_ -> BestAlly не проверю тип! Фактически, никакая функция, возвращающая элемент, отсутствующий в списке, который ей дан, не проверит тип (хотя некоторые функции, которые входят в бесконечные циклы или выдают ошибки и поэтому никогда не возвращают, будут делать это).
Вышесказанное придумано, конечно, но изменение этого метода является ключом к созданию ST Монада в безопасности.
Типы более высокого ранга не так экзотичны, как другие ответы. Хотите верьте, хотите нет, но многие объектно-ориентированные языки (включая Java и C#!) Поддерживают их. (Конечно, никто в этих сообществах не знает их под страшно звучащим названием "типы высшего ранга".)
В качестве примера я приведу учебную реализацию шаблона "Посетитель", которую я использую все время в своей повседневной работе. Этот ответ не предназначен как введение в шаблон посетителя; это знание легко доступно в другом месте.
В этом нелепом воображаемом приложении по кадрам мы хотим работать с сотрудниками, которые могут быть постоянными сотрудниками на постоянной основе или временными подрядчиками. Мой предпочтительный вариант шаблона посетителя (и действительно тот, который имеет отношение к RankNTypes) параметризует тип возврата посетителя.
interface IEmployeeVisitor<T>
{
T Visit(PermanentEmployee e);
T Visit(Contractor c);
}
class XmlVisitor : IEmployeeVisitor<string> { /* ... */ }
class PaymentCalculator : IEmployeeVisitor<int> { /* ... */ }
Дело в том, что несколько посетителей с разными типами возврата могут работать с одними и теми же данными. Это означает IEmployee не должен выражать мнение о том, что T должно быть.
interface IEmployee
{
T Accept<T>(IEmployeeVisitor<T> v);
}
class PermanentEmployee : IEmployee
{
// ...
public T Accept<T>(IEmployeeVisitor<T> v)
{
return v.Visit(this);
}
}
class Contractor : IEmployee
{
// ...
public T Accept<T>(IEmployeeVisitor<T> v)
{
return v.Visit(this);
}
}
Я хочу обратить ваше внимание на типы. Соблюдайте это IEmployeeVisitor универсально количественно определяет его тип возвращаемого значения, тогда как IEmployee количественно его внутри Accept метод - так сказать, на более высоком уровне. Перевод нелепо из C# в Haskell:
data IEmployeeVisitor r = IEmployeeVisitor {
visitPermanent :: PermanentEmployee -> r,
visitContractor :: Contractor -> r
}
newtype IEmployee = IEmployee {
accept :: forall r. IEmployeeVisitor r -> r
}
Так что у вас есть это. Типы более высокого ранга появляются в C#, когда вы пишете типы, содержащие универсальные методы.
Слайды из курса Хаскелла Брайана О'Салливана в Стэнфорде помогли мне понять Rank2Types,
Для тех, кто знаком с объектно-ориентированными языками, функция более высокого ранга - это просто универсальная функция, которая ожидает в качестве аргумента другую универсальную функцию.
Например, в TypeScript вы могли бы написать:
type WithId<T> = T & { id: number }
type Identifier = <T>(obj: T) => WithId<T>
type Identify = <TObj>(obj: TObj, f: Identifier) => WithId<TObj>
Посмотрите, как универсальный тип функции Identify требует универсальной функции типа Identifier? Это делает Identify функция более высокого ранга.