Злоупотребление алгеброй алгебраических типов данных - почему это работает? - PullRequest
275 голосов
/ 08 февраля 2012

«Алгебраическое» выражение для алгебраических типов данных выглядит очень наводящим на размышления тому, кто имеет опыт работы в математике. Позвольте мне попытаться объяснить, что я имею в виду.

Определив основные типы

  • Продукт
  • Союз +
  • Синглтон X
  • Единица 1

и используя сокращение для X•X и 2X для X+X и так далее, мы можем затем определить алгебраические выражения для, например, связанные списки

data List a = Nil | Cons a (List a)L = 1 + X • L

и бинарные деревья:

data Tree a = Nil | Branch a (Tree a) (Tree a)T = 1 + X • T²

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

L = 1 + X • L

(1 - X) • L = 1

L = 1 / (1 - X) = 1 + X + X² + X³ + ...

, где я использовал расширение ряда степеней 1 / (1 - X) совершенно неоправданным способом, чтобы получить интересный результат, а именно, что тип L имеет либо Nil, либо содержит 1 элемент, либо содержит 2 элементы или 3 и т. д.

Будет интереснее, если мы сделаем это для бинарных деревьев:

T = 1 + X • T²

X • T² - T + 1 = 0

T = (1 - √(1 - 4 • X)) / (2 • X)

T = 1 + X + 2 • X² + 5 • X³ + 14 • X⁴ + ...

снова, используя расширение серии power (сделано с Wolfram Alpha ). Это выражает неочевидный (для меня) факт, что существует только одно двоичное дерево с 1 элементом, 2 двоичных дерева с двумя элементами (второй элемент может находиться слева или справа), 5 двоичных деревьев с тремя элементами и т. Д. .

Итак, мой вопрос - что я здесь делаю? Эти операции кажутся неоправданными (что такое квадратный корень алгебраического типа данных?), Но они приводят к ощутимым результатам. имеет ли отношение два алгебраических типа данных какое-либо значение в информатике, или это просто нотационная хитрость?

И, возможно, более интересно, возможно ли расширить эти идеи? Существует ли теория алгебры типов, которая допускает, например, произвольные функции типов, или для типов требуется представление степенного ряда? Если вы можете определить класс функций, то имеет ли какое-либо значение композиция функций?

Ответы [ 7 ]

135 голосов
/ 08 февраля 2012

Отказ от ответственности: на самом деле многое из этого работает не совсем правильно, когда вы учитываете so, поэтому я буду просто игнорировать это ради простоты.

Несколько начальных пунктов:

  • Обратите внимание, что термин "объединение", вероятно, не является лучшим термином для A + B здесь - это конкретно a дизъюнкт union двух типов, потому что две стороны различаются, даже если их типы одинаковы.Что бы это ни стоило, более распространенный термин - просто «тип суммы».

  • Синглтон-типы - это, по сути, все типы единиц.Они ведут себя одинаково при алгебраических манипуляциях, и, что более важно, объем информации сохраняется до сих пор.

  • Вы, вероятно, также хотите иметь нулевой тип.Стандартного нет, но самое распространенное имя - Void.Нет значений с нулевым типом, точно так же, как есть одно значение с типом, равным единице.

Здесь все еще не хватает одной важной операции, но я вернусь к этому через минуту.

Как вы, наверное, заметили, Haskell имеет тенденцию заимствовать понятия из теории категорий, и все вышеперечисленное имеет очень простую интерпретацию как:

  • Данные объектыA и B в Hask , их произведение A × B является уникальным (с точностью до изоморфизма) типом, который допускает две проекции fst : A × B → A и snd : A × B → B, где заданы любой тип C и функции f : C → A, g : C → B вы можете определить сопряжение f &&& g : C → A × B так, что fst ∘ (f &&& g) = f и аналогично для g .Параметричность гарантирует универсальные свойства автоматически, и мой менее тонкий выбор имен должен дать вам представление.Кстати, оператор (&&&) определен в Control.Arrow.

  • Двойным из вышеперечисленного является побочный продукт A + B с инъекциями inl : A→ A + B и inr : B → A + B, где дан любой тип C и функции f : A → C, g : B → C,Вы можете определить сопряжение f |||g : A + B → C такой, что имеют место очевидные эквивалентности.Опять же, параметричность гарантирует большинство сложных деталей автоматически.В этом случае стандартными инъекциями являются просто Left и Right, а сопряжением является функция either.

Многие свойства типа продукта и суммы могут быть полученыиз вышесказанного.Обратите внимание, что любой одноэлементный тип является конечным объектом Hask , а любой пустой тип является начальным объектом.

Возвращаясь к вышеупомянутой отсутствующей операции в декартовой закрытой категории у вас есть экспоненциальные объекты , которые соответствуют стрелкам категории.Наши стрелки являются функциями, наши объекты являются типами типа *, а тип A -> B действительно ведет себя как B A в контексте алгебраической манипуляции типами.Если не понятно, почему это так, рассмотрим тип Bool -> A.Имея только два возможных входа, функция этого типа изоморфна двум значениям типа A, то есть (A, A).Для Maybe Bool -> A у нас есть три возможных входа и так далее.Кроме того, обратите внимание, что если мы перефразируем приведенное выше определение сопряжения для использования алгебраической записи, мы получим тождество C A × C B = C A + B .

Что касается , почему все это имеет смысл - и, в частности, почему использование расширения степенных рядов оправдано - обратите внимание, что большая часть из вышесказанного относится к "обитателям" типа(т. е. различные значения, имеющие этот тип), чтобы продемонстрировать алгебраическое поведение.Чтобы сделать эту перспективу явной:

  • Тип продукта(A, B) представляет значение, каждое из A и B, взятое независимо. Таким образом, для любого фиксированного значения a :: A существует одно значение типа (A, B) для каждого жителя B. Это, конечно, декартово произведение, а число жителей вида продукта является произведением числа жителей факторов.

  • Тип суммы Either A B представляет значение либо A, либо B с выделением левой и правой ветвей. Как упоминалось ранее, это несвязный союз, и число жителей типа суммы является суммой числа жителей слагаемых.

  • Экспоненциальный тип B -> A представляет собой отображение значений типа B на значения типа A. Для любого фиксированного аргумента b :: B ему может быть присвоено любое значение A; значение типа B -> A выбирает одно такое сопоставление для каждого ввода, что эквивалентно произведению такого количества копий A, которое имеет B жителей, следовательно возведение в степень.

Поначалу соблазнительно рассматривать типы как наборы, которые на самом деле не очень хорошо работают в этом контексте - у нас есть несвязанное объединение, а не стандартное объединение множеств, нет очевидной интерпретации пересечения или многих других операций над множествами и мы обычно не заботимся о членстве в наборе (оставляя это проверке типов).

С другой стороны, вышеприведенные конструкции проводят много времени, говоря о подсчете жителей и перечислении возможных значений типа, что является здесь полезной концепцией. Это быстро приводит нас к перечислительной комбинаторике , и если вы обратитесь к связанной статье в Википедии, вы обнаружите, что в первую очередь она определяет «пары» и «союзы» в том же смысле, что и продукт и суммировать типы посредством генерации функций , затем делает то же самое для «последовательностей», которые идентичны спискам в Haskell, используя точно такую ​​же технику, что и вы.


Редактировать: О, и вот быстрый бонус, который, я думаю, наглядно демонстрирует это. Вы упомянули в комментарии, что для типа дерева T = 1 + T^2 вы можете получить тождество T^6 = 1, что явно неверно. Однако, T^7 = T действительно , и биекция между деревьями и семью корнями деревьев может быть построена непосредственно, ср. «Семь деревьев в одном» Андреаса Бласса .

Редактировать × 2: По вопросу о конструкции «производного типа», упомянутой в других ответах, вам также может понравиться эта статья того же автора , основанная на Идея далее, в том числе понятия деления и другие интересные еще много чего.

43 голосов
/ 08 февраля 2012

Двоичные деревья определяются уравнением T=1+XT^2 в полукольце типов.По построению T=(1-sqrt(1-4X))/(2X) определяется тем же уравнением в полукольце комплексных чисел.Поэтому, учитывая, что мы решаем одно и то же уравнение в одном и том же классе алгебраической структуры, на самом деле не должно быть удивительно, что мы видим некоторое сходство.числами мы обычно используем тот факт, что комплексные числа образуют кольцо или даже поле, поэтому мы используем такие операции, как вычитание, которые не применяются к полукольцам.Но мы часто можем исключить вычитания из наших аргументов, если у нас есть правило, которое позволяет нам отменять обе части уравнения.Это то, что доказано Фиоре и Ленстером , показывающими, что многие аргументы о кольцах могут быть переданы в полукольца.

Это означает, что многие ваши математические знания о кольцах могут быть надежно переданытипы.В результате некоторые аргументы, включающие комплексные числа или степенные ряды (в кольце формальных степенных рядов), могут совершенно точно переноситься на типы.

Однако в этой истории есть кое-что еще.Одно дело доказать, что два типа равны (скажем), показав, что два степенных ряда равны.Но вы также можете получить информацию о типах, проверив термины в степенных рядах.Я не уверен, каким должно быть официальное заявление.(Я рекомендую бумагу Брента Йорги о комбинаторных видах для некоторых работ, которые тесно связаны, но виды не такие же, как типы.)

ЧтоЯ считаю совершенно невероятным, что то, что вы обнаружили, может быть расширено до исчисления.Теоремы об исчислении можно перенести на полукольцо типов.Фактически, даже аргументы о конечных разностях могут быть переданы, и вы обнаружите, что классические теоремы из численного анализа имеют интерпретации в теории типов.

Веселитесь!

20 голосов
/ 08 февраля 2012

Кажется, что все, что вы делаете, - это расширение отношения повторения.

L = 1 + X • L
L = 1 + X • (1 + X • (1 + X • (1 + X • ...)))
  = 1 + X + X^2 + X^3 + X^4 ...

T = 1 + X • T^2
L = 1 + X • (1 + X • (1 + X • (1 + X • ...^2)^2)^2)^2
  = 1 + X + 2 • X^2 + 5 • X^3 + 14 • X^4 + ...

И поскольку правила для операций над типами работают так же, как правила для арифметических операций, вы можете использовать алгебраические средства, чтобы помочь вам выяснить, как расширить рекуррентное отношение (поскольку это не очевидно).

18 голосов
/ 08 февраля 2012

У меня нет полного ответа, но эти манипуляции имеют тенденцию «просто работать».Соответствующей статьей может быть Объекты категорий в виде комплексных чисел Фьора и Ленстера - я наткнулся на эту статью, читая блог sigfpe по соответствующей теме ;остальная часть этого блога - золотая жила для подобных идей, и ее стоит проверить!

Кстати, вы также можете различать типы данных - это даст вам подходящую молнию для типа данных!

10 голосов
/ 13 июня 2012

Алгебра коммуникационных процессов (ACP) имеет дело с подобными выражениями для процессов.Он предлагает сложение и умножение в качестве операторов выбора и последовательности со связанными нейтральными элементами.На основании этого есть операторы для других конструкций, таких как параллелизм и нарушение.См. http://en.wikipedia.org/wiki/Algebra_of_Communicating_Processes. В Интернете также есть статья под названием «Краткая история алгебры процессов».

Я работаю над расширением языков программирования с помощью ACP.В апреле прошлого года я представил исследовательскую работу на Scala Days 2012, доступную по адресу http://code.google.com/p/subscript/

. На конференции я продемонстрировал отладчик, запускающий параллельную рекурсивную спецификацию пакета:

Bag = A;(Bag & a)

где A и подставка для действий ввода и вывода;точка с запятой и знак амперсанда означают последовательность и параллелизм.Смотрите видео на SkillsMatter, доступное по предыдущей ссылке.

Спецификация сумки, более сравнимая с

L = 1 + X • L

, будет

B = 1 + X & B

ACP определяет параллелизм в терминах выбора и последовательности с использованием аксиом;см. статью в Википедии.Интересно, какова будет аналогия с сумками для

L = 1 / (1-X)

Программирование в стиле ACP удобно для анализаторов текста и контроллеров GUI.Такие спецификации, как

searchCommand = clicked (searchButton) + key (Enter)

cancelCommand = clicked (cancelButton) + key (Escape)

могут быть записаны более кратко с помощьюсделав два уточнения «нажатыми» и «ключевыми» неявными (например, что Scala позволяет с функциями).Следовательно, мы можем написать:

searchCommand = searchButton + Enter

cancelCommand = cancelButton + Escape

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

Процессы получают таким образом данные в качестве компаньонов;таким образом, я использую термин «алгебра предметов».

6 голосов
/ 01 января 2017

серии исчисления и маклаурина с типами

Вот еще одно незначительное дополнение - комбинаторное понимание того, почему коэффициенты в разложении рядов должны «работать», в частности сосредоточение внимания на рядах, которые могут быть получены с использованием подхода Тейлора-Маклорина из исчисления. NB: пример раскрываемой вами серии манипулируемого типа списка - это серия Маклорина.

Поскольку другие ответы и комментарии касаются поведения выражений алгебраического типа (сумм, произведений и показателей степени), этот ответ исключит эти детали и сосредоточится на типе «исчисление».

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

  • Мы занимаемся предоставлением толкований из одной области сущностям из другой, и представляется целесообразным таким образом разграничить такие иностранные понятия.
  • некоторые понятия смогут формализоваться более строго, но форма и идеи кажутся более важными (и занимают меньше места для написания), чем детали.

Определение серии Маклаурин

Серия Maclaurin функции f : ℝ → ℝ определяется как

f(0) + f'(0)X + (1/2)f''(0)X² + ... + (1/n!)f⁽ⁿ⁾(0)Xⁿ + ...

, где f⁽ⁿ⁾ означает n th производную от f.

Чтобы иметь возможность понять серию Maclaurin как интерпретируемую с типами, нам нужно понять, как мы можем интерпретировать три вещи в контексте типов:

  • (возможно, несколько) производных
  • применение функции к 0
  • такие термины, как (1/n!)

и оказывается, что у этих концепций из анализа есть подходящие аналоги в мире типов.

Что я имею в виду под «подходящим партнером»? Он должен иметь вид изоморфизма - если мы можем сохранить истину в обоих направлениях, факты, полученные в одном контексте, могут быть перенесены в другой.

Исчисление с типами

Так, что означает производная выражения типа? Оказывается, что для большого и корректного («дифференцируемого») класса выражений типов и функторов существует естественная операция, которая ведет себя достаточно схожим образом, чтобы быть подходящей интерпретацией!

Чтобы испортить изюминку, операция, аналогичная дифференцированию, заключается в создании «контекстов с одной дырой». Это является отличным местом для дальнейшего раскрытия этой конкретной точки, но основная концепция контекста с одним отверстием (da/dx) заключается в том, что он представляет собой результат извлечения одного подпункта определенного типа (x) из термина (типа a), сохраняющего всю другую информацию, включая ту, которая необходима для определения исходного местоположения подпункта. Например, один из способов представления контекста с одним отверстием для списка - два списка: один для элементов, которые были до извлеченного, и один для элементов, следующих за.

Мотивация для идентификации этой операции с дифференцированием исходит из следующих наблюдений. Мы пишем da/dx, чтобы обозначить тип контекстов с одним отверстием для типа a с отверстием типа x.

d1/dx = 0
dx/dx = 1
d(a + b)/dx = da/dx + db/dx
d(a × b)/dx = a × db/dx + b × da/dx
d(g(f(x))/dx = d(g(y))/dy[f(x)/a] × df(x)/dx

Здесь 1 и 0 представляют типы с ровно одним и ровно нулевым населением соответственно, а + и × представляют суммы и типы продуктов как обычно. f и g используются для представления функций типа или формирователей выражений типа, а [f(x)/a] означает операцию замены f(x) для каждого a в предыдущем выражении.

Это можно записать в стиле без точек, написав f' для обозначения производной функции типа function f, таким образом:

(x ↦ 1)' = x ↦ 0
(x ↦ x)' = x ↦ 1
(f + g)' = f' + g'
(f × g)' = f × g' + g × f'
(g ∘ f)' = (g' ∘ f) × f'

, что может быть предпочтительнее.

NB. Равенства можно сделать строгими и точными, если мы определим производные, используя классы изоморфизма типов и функторов.

Теперь отметим, в частности, что правила исчисления, относящиеся к алгебраическим операциям сложения, умножения и композиции (часто называемые правилами сумм, произведений и цепочек), отражаются именно операцией «создания отверстия».».Кроме того, базовые случаи «создания дыры» в постоянном выражении или сам термин x также ведут себя как дифференцирование, поэтому по индукции мы получаем дифференцирующее поведение для всех выражений алгебраического типа.

Теперь мы можем интерпретировать дифференцирование, что означает n th 'производная' выражения типа dⁿe/dxⁿ?Это тип, представляющий контексты n: термины, которые при «заполнении» n терминами типа x дают e.Есть еще одно ключевое наблюдение, связанное с появлением '(1/n!)' позже.

Инвариантная часть функтора типа: применение функции к 0

У нас уже есть интерпретация для 0 вМир типов: пустой тип без членов.Что это означает, с комбинаторной точки зрения, применить к нему функцию типа?Если говорить более конкретно, предположим, что f является функцией типа, как выглядит f(0)?Ну, у нас, конечно, нет доступа ни к чему типу 0, поэтому любые конструкции f(x), которые требуют x, недоступны.Остались те термины, которые доступны в их отсутствие, которые мы можем назвать «инвариантной» или «константной» частью типа.

Для явного примера возьмем функтор Maybe, который можетбыть представленным алгебраически как x ↦ 1 + x.Когда мы применяем это к 0, мы получаем 1 + 0 - это похоже на 1: единственное возможное значение - это значение None.Аналогично, для списка мы получаем только термин, соответствующий пустому списку.

Когда мы возвращаем его и интерпретируем тип f(0) как число, его можно считать числом от того, сколько терминов типа f(x) (для любого x) можно получить без доступа к x: то есть количеству «пустых» терминов.

Помещениевместе: полная интерпретация серии Маклаурина

Боюсь, я не могу представить себе подходящую прямую интерпретацию (1/n!) как типа.

Если мы рассмотрим, однако, типf⁽ⁿ⁾(0) в свете вышесказанного мы видим, что его можно интерпретировать как тип n -контекстов для термина типа f(x), который еще не содержит x -то есть, когда мы «интегрируем» их n раза, результирующий термин будет иметь точно n x с, не больше, не меньше.Тогда интерпретация типа f⁽ⁿ⁾(0) как числа (как в коэффициентах ряда Маклаурина f) представляет собой просто подсчет количества таких пустых контекстов n.Мы почти на месте!

Но где же заканчивается (1/n!)?Изучение процесса типа «дифференцирование» показывает нам, что при многократном применении он сохраняет «порядок», в котором извлекаются подтермы.Например, рассмотрим термин (x₀, x₁) типа x × x и операцию «проделать дыру» в нем дважды.Мы получаем обе последовательности

(x₀, x₁)  ↝  (_₀, x₁)  ↝  (_₀, _₁)
(x₀, x₁)  ↝  (x₀, _₀)  ↝  (_₁, _₀)
(where _ represents a 'hole')

, хотя обе они происходят от одного и того же термина, потому что есть 2! = 2 способов взять два элемента из двух, сохраняя порядок.В целом, существует n! способов получения n элементов из n.Таким образом, чтобы получить количество конфигураций типа функтора, которые имеют n элементов, мы должны посчитать тип f⁽ⁿ⁾(0) и разделить на n!, точно , как в коэффициентахиз серии Маклаурина.

Таким образом, деление на n! оказывается интерпретируемым просто как само по себе.

Заключительные мысли: «рекурсивные» определения и аналитичность

Во-первых, некоторыенаблюдения:

  • если функция f: ℝ → ℝ имеет производную, эта производная уникальна
  • аналогично, если функция f: ℝ → analy аналитическая, она имеет ровно однусоответствующий полиномиальный ряд

Су нас есть правило цепочки, мы можем использовать неявное дифференцирование , если мы формализуем производные типа как классы изоморфизма. Но неявное дифференцирование не требует каких-либо инопланетных маневров, таких как вычитание или деление! Таким образом, мы можем использовать его для анализа определений рекурсивных типов. Чтобы взять пример списка, у нас есть

L(X) ≅ 1 + X × L(X)
L'(X) = X × L'(X) + L(X)

и тогда мы можем оценить

L'(0) = L(0) = 1

для получения коэффициента в серии Маклаурина.

Но поскольку мы уверены, что эти выражения действительно строго «дифференцируемы», хотя бы неявно, и поскольку мы имеем соответствие с функциями ℝ → ℝ, где производные, безусловно, уникальны, мы можем быть уверены, что даже если мы получим значения с использованием «незаконных» операций, результат действителен.

Теперь, аналогично, используем второе наблюдение из-за соответствия (это гомоморфизм?) Функциям ℝ → ℝ, мы знаем, что при условии, что мы удовлетворены тем, что функция имеет Маклаурина серии, если мы можем найти любую серию вообще , принципы, изложенные выше, могут быть применены, чтобы сделать ее строгой.

Что касается вашего вопроса о композиции функций, я полагаю, что правило цепочки дает частичный ответ.

Я не уверен, к какому числу ADT в стиле Haskell это относится, но я подозреваю, что их много, если не все. Я обнаружил поистине изумительное доказательство этого факта, но этот запас слишком мал, чтобы его содержать ...

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

Резюме: TL; DR

  • тип 'дифференцирование' соответствует ', делающему отверстие '.
  • применение функтора к 0 дает нам «пустые» термины для этого функтора.
  • Maclaurin степенные ряды, поэтому (несколько) строго соответствуют перечислению числа членов типа функтора с определенным количеством элементов.
  • неявная дифференциация делает это более водонепроницаемым.
  • уникальность производных и уникальность степенных рядов означает, что мы можем выдумать детали, и это работает.
4 голосов
/ 04 февраля 2017

Теория зависимого типа и функции произвольного типа

Мой первый ответ на этот вопрос был высоким на концепциях и низким уровнем детализации и отражал подвопрос «что происходит?»; этот ответ будет таким же, но сфокусирован на вопросе: «можем ли мы получить функции произвольного типа?».

Одним из расширений алгебраических операций суммы и произведения являются так называемые «большие операторы», которые представляют сумму и произведение последовательности (или, в более общем случае, сумму и произведение функции над областью), обычно записываемой Σ и Π соответственно. См. Сигма нотация .

Итак, сумма

a₀ + a₁X + a₂X² + ...

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

Σ[i ∈ ℕ]aᵢXⁱ

где a - это, например, некоторая последовательность действительных чисел. Продукт будет представлен аналогично с Π вместо Σ.

Когда вы смотрите с расстояния, выражение такого типа очень похоже на «произвольную» функцию в X; конечно, мы ограничены выразимыми рядами и связанными с ними аналитическими функциями. Это кандидат на представление в теории типов? Определенно!

Класс теорий типов, которые имеют непосредственные представления этих выражений, является классом теорий «зависимых» типов: теорий с зависимыми типами. Естественно, у нас есть термины, зависящие от терминов, и в таких языках, как Haskell, с функциями типов и определением типов, терминами и типами в зависимости от типов. В зависимом окружении у нас также есть типы в зависимости от условий. Haskell не является языком с зависимой типизацией, хотя многие свойства зависимых типов можно смоделировать , немного помучив язык .

Карри-Ховард и зависимые типы

«Изоморфизм Карри-Говарда» начал свою жизнь как наблюдение того, что термины и правила оценки типов лямбда-исчисления с простыми типами в точности соответствуют естественному дедукции (сформулированной Генценом), примененной к интуиционистской логике высказываний, причем типы принимают место предложений и термины, заменяющие доказательства, несмотря на то, что оба они были изобретены / открыты независимо друг от друга. С тех пор это стало огромным источником вдохновения для теоретиков типов. Одна из наиболее очевидных вещей, которую следует рассмотреть, - может ли и как это соответствие для логики высказываний быть распространено на логики предикатов или логики более высокого порядка. Теории зависимого типа изначально возникли на этом пути исследования.

Для ознакомления с изоморфизмом Карри-Ховарда для простейшего типа лямбда-исчисления см. здесь . Например, если мы хотим доказать A ∧ B, мы должны доказать A и доказать B; комбинированное доказательство - это просто пара доказательств: по одному на каждое соединение.

При естественном удержании:

Γ ⊢ A    Γ ⊢ B
Γ ⊢ A ∧ B

и в простом наборе лямбда-исчисления:

Γ ⊢ a : A    Γ ⊢ b : B
Γ ⊢ (a, b) : A × B

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

Недоказуемое (интуитивно ложное) суждение соответствует необитаемому типу.

Имея в виду аналогию типов как логических суждений, мы можем начать думать о том, как моделировать предикаты в мире типов. Есть много способов, которыми это было формализовано (см. это введение к Интуиционистской Теории Типа Мартина-Лёфа для широко используемого стандарта), но абстрактный подход обычно отмечает, что предикат подобен предложению со свободным термином переменные или, альтернативно, функция, принимающая термины в суждения. Если мы допустим, чтобы выражения типов содержали термины, то обработка в стиле лямбда-исчисления сразу же представилась бы возможностью!

Учитывая только конструктивные доказательства, что составляет доказательство ∀x ∈ X.P(x)? Мы можем думать об этом как о функции доказательства, переводя члены (x) в доказательства их соответствующих предложений (P(x)). Таким образом, члены (доказательства) типа (предложения) ∀x : X.P(x) являются «зависимыми функциями», которые для каждого x в X дают член типа P(x).

А как насчет ∃x ∈ X.P(x)?Нам нужен любой член X, x вместе с доказательством P(x).Таким образом, члены (доказательства) типа (предложения) ∃x : X.P(x) являются «зависимыми парами»: выделенный термин x в X вместе с термином типа P(x).

Обозначения: Iбудет использовать

∀x ∈ X...

для фактических утверждений о членах класса X и

∀x : X...

для выражений типа, соответствующих универсальному количественному определению над типом X.Аналогично для .

Комбинаторные соображения: произведения и суммы

Так же как соответствие типов Карри-Ховарда с предложениями, мы имеем комбинаторное соответствие алгебраических типов с числами и функциями,что является основным пунктом этого вопроса.К счастью, это может быть расширено до зависимых типов, описанных выше!

Я буду использовать обозначение модуля

|A|

, чтобы представить «размер» типа A, чтобы сделать явнымсоответствие, изложенное в вопросе, между типами и числами.Обратите внимание, что это понятие вне теории;Я не утверждаю, что в языке должен быть какой-либо такой оператор.

Давайте посчитаем возможные (полностью сокращенные, канонические) члены типа

∀x : X.P(x)

, который является типом зависимогофункции, принимающие термины x типа X в термины типа P(x).Каждая такая функция должна иметь выход для каждого члена X, и этот вывод должен быть определенного типа.Таким образом, для каждого x в X это дает |P(x)| «вариантов» вывода.

Изюминка -

|∀x : X.P(x)| = Π[x : X]|P(x)|

, что, конечно, не имеет большого значенияимеет смысл, если X равно IO (), но применимо к алгебраическим типам.

Аналогично, термин типа

∃x : X.P(x)

является типом пар (x, p) с p : P(x), поэтому с учетом любого x в X мы можем построить подходящую пару с любым членом P(x), что дает |P(x)| 'выборы'.

Следовательно,

|∃x : X.P(x)| = Σ[x : X]|P(x)|

с такими же оговорками.

Это оправдывает общее обозначение зависимых типов в теориях, использующих символы Π и Σ, и на самом деле многие теории стирают различие между «для всех» и «продуктом» имежду «есть» и «сумма» из-за вышеупомянутых соответствий.

Мы приближаемся!

Векторы: представляющие зависимые кортежи

Можем ли мы теперь кодироватьчисловые выражения типа

Σ[n ∈ ℕ]Xⁿ

как выражения типа?

Не совсем.Хотя мы можем неофициально рассмотреть значение таких выражений, как Xⁿ в Haskell, где X - это тип, а n - натуральное число, это злоупотребление нотацией;это выражение типа, содержащее число: отчетливо не допустимое выражение.

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

Для продолжительности этого ответа пусть

Vec X n

будет типом длины- n векторов значений X -типа.

Технически n здесь, вместо фактического натурального числа, представление всистема натурального числа.Мы можем представить натуральные числа (Nat) в стиле Пеано как ноль (0) или преемник (S) другого натурального числа, а для n ∈ ℕ я пишу ˻n˼, чтобы обозначить термин в Nat, что представляет n.Например, ˻3˼ равно S (S (S 0)).

Тогда у нас есть

|Vec X ˻n˼| = |X|ⁿ

для любых типов n ∈ ℕ.

Nat: продвижение ℕ терминов в типы

Теперь мы можем кодировать выражения вроде

Σ[n ∈ ℕ]Xⁿ

как типы. Это конкретное выражение приведет к типу, который, конечно, изоморфен типу списков X, как указано в вопросе. (Не только это, но и с точки зрения теории категорий, функция типа - которая является функтором - перевод X к указанному выше типу естественно изоморфна в Список функтор.)

Последний фрагмент головоломки для «произвольных» функций - как кодировать, для

f : ℕ → ℕ

выражения типа

Σ[n ∈ ℕ]f(n)Xⁿ

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

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

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

Существует несколько способов представления типов на уровне терминов. Я буду использовать здесь воображаемую запись Хаскеллиша с * для вселенной типов, которая обычно считается типом в зависимом окружении. 1

Аналогично, существует также, по крайней мере, столько способов записать ' -элиминацию', сколько существует зависимых теорий типов. Я буду использовать Haskellish для сопоставления с образцом.

Нам нужно отображение α от Nat до *, со свойством

∀n ∈ ℕ.|α ˻n˼| = n.

Достаточно следующего псевдоопределения.

data Zero -- empty type
data Successor a = Z | Suc a -- Successor ≅ Maybe

α : Nat -> *
α 0 = Zero
α (S n) = Successor (α n)

Итак, мы видим, что действие α отражает поведение преемника S, что делает его своего рода гомоморфизмом. Successor - это функция типа, которая «добавляет единицу» к числу членов типа; |Successor a| = 1 + |a| для любого a с заданным размером.

Например α ˻4˼ (что α (S (S (S (S 0))))), это

Successor (Successor (Successor (Successor Zero)))

и условия этого типа

Z
Suc Z
Suc (Suc Z)
Suc (Suc (Suc Z))

дает нам ровно четыре элемента: |α ˻4˼| = 4.

Аналогично, для любого n ∈ ℕ у нас есть

|α ˻n˼| = n

по мере необходимости.

  1. Многие теории требуют, чтобы члены * были просто представителями типов, а операция предоставляется в виде явного отображения терминов типа * в связанные с ними типы. Другие теории допускают, чтобы сами литеральные типы были сущностями уровня термина.

'Произвольные' функции?

Теперь у нас есть аппарат для выражения общего общего степенного ряда как типа!

Серия

Σ[n ∈ ℕ]f(n)Xⁿ

становится типом

∃n : Nat.α (˻f˼ n) × (Vec X n)

, где ˻f˼ : Nat → Nat - некоторое подходящее представление на языке функции f. Мы можем видеть это следующим образом.

|∃n : Nat.α (˻f˼ n) × (Vec X n)|
    = Σ[n : Nat]|α (˻f˼ n) × (Vec X n)|          (property of ∃ types)
    = Σ[n ∈ ℕ]|α (˻f˼ ˻n˼) × (Vec X ˻n˼)|        (switching Nat for ℕ)
    = Σ[n ∈ ℕ]|α ˻f(n)˼ × (Vec X ˻n˼)|           (applying ˻f˼ to ˻n˼)
    = Σ[n ∈ ℕ]|α ˻f(n)˼||Vec X ˻n˼|              (splitting product)
    = Σ[n ∈ ℕ]f(n)|X|ⁿ                           (properties of α and Vec)

Насколько это «произвольно»? Этот метод ограничен не только целыми коэффициентами, но и натуральными числами. Кроме того, f может быть чем угодно, учитывая, что Turing Complete с зависимыми типами, мы можем представить любую аналитическую функцию с натуральными числовыми коэффициентами.

Я не исследовал взаимодействие этого, например, со случаем, приведенным в вопросе List X ≅ 1/(1 - X), или каков возможный смысл таких отрицательных и нецелочисленных «типов» в этом контексте.

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

...