Индуктивный тип - Википедия - Inductive type

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

Стандартный пример кодирует натуральные числа с помощью Кодировка Пеано.

 Индуктивный нац : Тип :=   | 0 : нац   | S : нац -> нац.

Здесь натуральное число создается либо из константы «0», либо путем применения функции «S» к другому натуральному числу. "S" - это функция преемника что представляет собой прибавление 1 к числу. Таким образом, «0» равен нулю, «S 0» равен единице, «S (S 0)» равен двум, «S (S (S 0))» равен трем и так далее.

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

Устранение

Индуктивные типы обычно имеют функцию, чтобы доказать свои свойства. Таким образом, «нат» может иметь:

 nat_elim : (для всех п : нац -> Опора, (п 0) -> (для всех п, п п -> п (S п)) -> (для всех п, п п)).

Это ожидаемая функция структурной рекурсии для типа «nat».

Реализации

W- и M-типы

W-типы обоснованный типы в интуиционистская теория типов (ITT).^[1] Они обобщают натуральные числа, списки, двоичные деревья и другие "древовидные" типы данных. Позволять U быть вселенная типов. Учитывая тип А : U и зависимая семья B : А → U, можно образовать W-тип ${ displaystyle { mathsf {W}} _ {a: A} B (a)}$ . Тип А можно рассматривать как "метки" для (потенциально бесконечного множества) конструкторов определяемого индуктивного типа, тогда как B указывает (потенциально бесконечное) арность каждого конструктора. W-типы (соответственно M-типы) также можно понимать как хорошо обоснованные (или необоснованные) деревья с узлами, помеченными элементами а : А и где узел, помеченный а имеет B(а) -много поддеревьев.^[2] Каждый W-тип изоморфен исходной алгебре так называемого полиномиальный функтор.

Позволять 0, 1, 2и т. д. быть конечными типами с жителями 1₁ : 1, 1₂, 2₂:2и т.д. Натуральные числа можно определить как W-тип

{ Displaystyle mathbb {N}: = { mathsf {W}} _ {x: mathbf {2}} f (x)}

с ж : 2 → U определяется ж(1₂) = 0 (представляющий конструктор для нуля, который не принимает аргументов) и ж(2₂) = 1 (представляющая функцию-преемник, которая принимает один аргумент).

Можно определять списки по типу А : U в качестве ${ displaystyle operatorname {List} (A): = { mathsf {W}} _ {(x: mathbf {1} + A)} f (x)}$ куда

{ displaystyle { begin {align} f ( operatorname {inl} (1 _ { mathbf {1}})) & = mathbf {0} f ( operatorname {inr} (a)) & = mathbf {1} конец {выровнено}}}

и 1₁ единственный житель 1. Значение ${ Displaystyle е ( OperatorName {inl} (1 _ { mathbf {1}}))}$ соответствует конструктору пустого списка, тогда как значение ${ Displaystyle е ( OperatorName {inr} (а))}$ соответствует конструктору, который добавляет а в начало другого списка.

Конструктор элементов универсального W-типа ${ Displaystyle { mathsf {W}} _ {x: A} B (x)}$ имеет тип

{ Displaystyle { mathsf {sup}}: prod _ {a: A} { Big (} B (a) to { mathsf {W}} _ {x: A} B (x) { Big )} to { mathsf {W}} _ {x: A} B (x).}

Мы также можем написать это правило в стиле естественный вычет доказательство,

{ displaystyle { frac {a: A qquad f: B (a) to { mathsf {W}} _ {x: A} B (x)} {{ mathsf {sup}} (a, f ): { mathsf {W}} _ {x: A} B (x)}}.}

Правило исключения для W-типов работает аналогично структурная индукция на деревьях. Если когда-либо свойство (под предложения как типы интерпретация) ${ Displaystyle C: { mathsf {W}} _ {x: A} B (x) to U}$ выполняется для всех поддеревьев данного дерева, оно также выполняется для этого дерева, тогда оно выполняется для всех деревьев.

{ displaystyle { frac {w: { mathsf {W}} _ {a: A} B (a) qquad a: A, ; f: B (a) to { mathsf {W}} _ {x: A} B (x), ; c: prod _ {b: B (a)} C (f (b)) ; vdash ; h (a, f, c): C ({ mathsf {sup}} (a, f))} {{ mathsf {elim}} (w, h): C (w)}}}

В теориях экстенсиональных типов W-типы (соответственно M-типы) могут быть определены с точностью до изоморфизм в качестве начальные алгебры (соответственно финальные коалгебры) для полиномиальные функторы. В этом случае свойство начальности (окончательности) прямо соответствует соответствующему принципу индукции.^[3] В теориях интенсионального типа с аксиома однолистности, это соответствие выполняется с точностью до гомотопии (пропозиционального равенства).^[4]^[5]^[6]

M-типы двойной к W-типам они представляют коиндуктивный (потенциально бесконечные) данные, такие как потоки.^[7] M-типы могут быть производными от W-типов.^[8]

Взаимно индуктивные определения

Этот метод позволяет немного определения нескольких типов, которые зависят друг от друга. Например, определение двух паритет предикаты на натуральные числа используя два взаимно индуктивных типа в Coq:

Индуктивный четное : нац -> Опора :=  | zero_is_even : четное О  | S_of_odd_is_even : (для всех п:нац, странный п -> четное (S п))с странный : нац -> Опора :=  | S_of_even_is_odd : (для всех п:нац, четное п -> странный (S п)).

Индукция-рекурсия

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

Типы вселенной можно определить с помощью индукции-рекурсии.

Индукция-индукция

Индукция-индукция позволяет одновременно определять тип и семейство типов. Итак, тип $А$ и семейство типов ${ displaystyle B: A to Type}$ .

Высшие индуктивные типы

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

Простой пример - $круг$ тип, который определяется двумя конструкторами, базовой точкой;

основание : круг

и петля;

петля : основание = основание .

Наличие нового конструктора для типа удостоверения делает $круг$ высший индуктивный тип.

Смотрите также

Коиндукция разрешает (эффективно) бесконечные структуры в теории типов.

внешняя ссылка

[1] Мартин-Лёф, Пер (1984). Интуиционистская теория типов (PDF). Самбин, Джованни. Неаполь: Библиополис. ISBN 8870881059. OCLC 12731401.

[2] Аренс, Бенедикт; Каприотти, Паоло; Спадотти, Режис (12 апреля 2015 г.). «Необоснованные деревья в теории гомотопических типов». arXiv:1504.02949. Дои:10.4230 / LIPIcs.TLCA.2015.17. Цитировать журнал требует | журнал = (помощь)

[3] Дибьер, Питер (1997). «Представление индуктивно определенных множеств с помощью порядков в теории типов Мартина-Лёфа». Теоретическая информатика. 176 (1–2): 329–335. Дои:10.1016 / s0304-3975 (96) 00145-4.

[4] Awodey, Стив; Гамбино, Никола; Соякова, Кристина (18.01.2012). «Индуктивные типы в теории гомотопических типов». arXiv:1201.3898 [math.LO ].

[5] Аренс, Бенедикт; Каприотти, Паоло; Спадотти, Режис (12 апреля 2015 г.). «Необоснованные деревья в теории гомотопических типов». arXiv:1504.02949. Дои:10.4230 / LIPIcs.TLCA.2015.17. Цитировать журнал требует | журнал = (помощь)

[6] Awodey, Стив; Гамбино, Никола; Соякова, Кристина (21.04.2015). «Гомотопически-начальные алгебры в теории типов». arXiv:1504.05531 [math.LO ].

[7] ван ден Берг, Бенно; Марчи, Федерико Де (2007). «Необоснованные деревья по категориям». Анналы чистой и прикладной логики. 146 (1): 40–59. arXiv:математика / 0409158. Дои:10.1016 / j.apal.2006.12.001.

[8] Эбботт, Майкл; Альтенкирх, Торстен; Гани, Нил (2005). «Контейнеры: конструирование строго положительных типов». Теоретическая информатика. 342 (1): 3–27. Дои:10.1016 / j.tcs.2005.06.002.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]