Контейнер (теория типов)

В теории типов , дисциплине математической логики, контейнеры различные «типы коллекций», такие как списки и деревья — это абстракции, которые позволяют единообразным образом представлять . ( Унарный ) контейнер определяется типом фигур S и семейством типов позиций P, индексируемым S. Расширением контейнера является семейство зависимых пар, состоящих из фигуры (типа S) и функции из позиций этой формы к типу элемента. Контейнеры можно рассматривать как канонические формы типов коллекций. ^[1]

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

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

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

Одной из основных причин введения понятия контейнеров является поддержка универсального программирования в условиях зависимой типизации . ^[1]

Категориальные аспекты

Расширением контейнера является эндофунктор . Требуется функция g к

\lambda (s,f).(s,g\circ f)

Это эквивалентно знакомому map g в случае списков и делает нечто подобное для других контейнеров.

Индексированные контейнеры

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

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

См. также

Ссылки

^ Jump up to: ^а ^б Майкл Эбботт; Торстен Альтенкирх; Нил Гани (2005). «Контейнеры: построение строго положительных типов» . Теоретическая информатика . 342 (1): 3–27. CiteSeerX 10.1.1.166.34 . дои : 10.1016/j.tcs.2005.06.002 .
^ Торстен Альтенкирх, Нил Гани, Питер Хэнкок, Конор МакБрайд и Питер Моррис. «Индексированные контейнеры» (PDF) . Неопубликованная рукопись . Проверено 30 октября 2008 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь ) CS1 maint: несколько имен: список авторов ( ссылка )

Внешние ссылки

о типах контейнеров Блог

\Gamma \!\vdash

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

[containers-1] Jump up to: ^а ^б Майкл Эбботт; Торстен Альтенкирх; Нил Гани (2005). «Контейнеры: построение строго положительных типов» . Теоретическая информатика . 342 (1): 3–27. CiteSeerX 10.1.1.166.34 . дои : 10.1016/j.tcs.2005.06.002 .

[indexed-containers-2] Торстен Альтенкирх, Нил Гани, Питер Хэнкок, Конор МакБрайд и Питер Моррис. «Индексированные контейнеры» (PDF) . Неопубликованная рукопись . Проверено 30 октября 2008 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь ) CS1 maint: несколько имен: список авторов ( ссылка )

[1]

[2]