Halkell singletons: Что мы получаем с SNat

Я пытаюсь вырвать синглы Haskell.

В статье Зачарованное программирование с помощью синглтонов и в своем блоге singletons v0.9 Released! Ричард Эйзенберг определяет тип данных Nat, который определяет натуральные числа с аксиомами peano:

data Nat = Zero | Succ Nat

Используя расширение языка DataKinds, этот тип данных повышается до уровня типа. Составляющие данных Zero и Succ продвигаются к конструкторам типа Zero и Succ. С этим мы получаем для каждого натурального числа единственный и уникальный соответствующий тип на уровне типа. Например, для 3 мы получаем "Succ (" Succ ( "Succ" Zero)). Итак, теперь у нас есть натуральные числа как типы.

Затем он определяет на уровне значения функцию плюс и на уровне типа тип семейства Plus чтобы операция добавления была доступна. С помощью функции продвижения/квазиготератора библиотеки синглтонов мы можем автоматически создайте семейство "Плюс" из функции "плюс". Поэтому мы можем избежать написания семейства типов.

До сих пор так хорошо!

С синтаксисом GADT он также определяет тип данных SNat:

data SNat :: Nat -> * where
  SZero :: SNat Zero
  SSucc :: SNat n -> SNat (Succ n)

В основном он только переносит тип Nat в конструктор SNat. Почему это необходимо? Что мы получаем? Являются ли типы данных Nat и SNat не изоморфными? Почему SNat синглтон, и почему Nat не синглтон? В обоих случаях каждый тип населен одним единственным значением, соответствующим натуральным числом.

Ответ 1

Что мы получаем? Хм. Статус синглтонов - это неловкое, но в настоящее время необходимое обходное решение, и чем скорее мы сможем справиться с ними, тем лучше.

Позвольте мне посмотреть, смогу ли я прояснить картину. У нас есть тип данных Nat:

data Nat = Zero | Suc Nat

(войны начались еще более тривиальными проблемами, чем число "c в Suc)

Тип Nat имеет значения времени выполнения, которые неотличимы на уровне типа. Система типа Haskell в настоящее время имеет свойство замены, а это означает, что в любой хорошо типизированной программе вы можете заменить любое хорошо выраженное подвыражение альтернативным подвыражением с тем же масштабом и типом, и программа будет по-прежнему хорошо набираться. Например, вы можете переписать каждое событие

if <b> then <t> else <e>

if <b> then <e> else <t>

и вы можете быть уверены, что ничего не пойдет не так... с результатом проверки вашего типа программы.

Замена собственности является смущением. Это явное доказательство того, что ваша система типов сдается в тот момент, когда смысл начинает иметь значение.

Теперь, будучи типом данных для значений времени выполнения, Nat также становится типом значений уровня 'Zero и 'Suc. Последние живут только на языке типа Haskell и вообще не имеют присутствия во время выполнения. Обратите внимание, что хотя типы 'Zero и 'Suc существуют на уровне типа, бесполезно ссылаться на них как на "типы", и люди, которые в настоящее время делают это, должны воздерживаться. Они не имеют типа * и поэтому не могут классифицировать значения, которые являются типами, достойными имени.

Нет прямых средств обмена между временем выполнения и типом уровня Nat s, что может быть неприятным. Парадигматический пример касается ключевой операции над векторами:

data Vec :: Nat -> * -> * where
  VNil   :: Vec 'Zero x
  VCons  :: x -> Vec n x -> Vec ('Suc n) x

Нам может потребоваться вычислить вектор копий данного элемента (возможно, как часть экземпляра Applicative). Может показаться хорошей идеей дать тип

vec :: forall (n :: Nat) (x :: *). x -> Vec n x

но может ли это работать? Чтобы сделать n копии чего-то, нам нужно знать n во время выполнения: программе необходимо решить, следует ли развертывать VNil и останавливать или развертывать VCons и продолжать работу, и для этого нужны некоторые данные для этого. Хорошей подсказкой является квантор forall, который является параметрическим: он указывает, что количественная информация доступна только для типов и стирается во время выполнения.

В настоящее время Haskell применяет полностью ложное совпадение между зависимой квантификацией (что делает forall) и стирает для времени выполнения. Он не поддерживает зависимый, но не удаленный квантификатор, который мы часто называем pi. Тип и реализация vec должны быть чем-то вроде

vec :: pi (n :: Nat) -> forall (x :: *). Vec n x
vec 'Zero    x = VNil
vec ('Suc n) x = VCons x (vec n x)

где аргументы в pi -позициях записываются на языке типов, но данные доступны во время выполнения.

Так что же мы делаем? Мы используем синглтоны для косвенного косвенного определения того, что значит быть копией данных типа уровня во время выполнения.

data SNat :: Nat -> * where
  SZero :: SNat Zero
  SSuc  :: SNat n -> SNat (Suc n)

Теперь SZero и SSuc введите данные во время выполнения. SNat не изоморфен Nat: первый имеет тип Nat -> *, а последний имеет тип *, поэтому это ошибка типа, чтобы попытаться сделать их изоморфными. В Nat есть много значений времени выполнения, и система типов не различает их; в каждой разной SNat n есть ровно одно значение времени выполнения (стоит говорить), поэтому тот факт, что система типов не может их отличить, не относится к этой точке. Дело в том, что каждый SNat n является другим типом для каждого другого n, и что сопоставление шаблона GADT (где шаблон может быть более конкретного экземпляра типа GADT, который, как известно, является совпадением), может улучшить наши знания of n.

Теперь мы можем написать

vec :: forall (n :: Nat). SNat n -> forall (x :: *). x -> Vec n x
vec SZero    x = VNil
vec (SSuc n) x = VCons x (vec n x)

Синглеты позволяют нам преодолеть разрыв между временем выполнения и данными уровня на уровне, используя единственную форму анализа времени выполнения, которая позволяет уточнить информацию о типе. Весьма разумно задаться вопросом, действительно ли они нужны, и в настоящее время они существуют, только потому, что этот пробел еще не устранен.