Список объектов - List object

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

Формальное определение

Позволять C быть категория с конечным товары и конечный объект 1. А список объектов над объект А из C является:

  1. объект LА,
  2. а морфизм оА : 1 → LА, и
  3. морфизм sА : А × LА → LА

такое, что для любого объекта B из C с картами б : 1 → B и т : А × B → B, существует единственный ж : LА → B такая, что следующая диаграмма ездит на работу:

Коммутативная диаграмма, выражающая уравнения в определении объекта списка

где 〈idА, ж〉 Обозначает стрелку, индуцированную универсальная собственность продукта при применении к idА (личность на А) и ж. Обозначение А* (а ля Клини звезда ) иногда используется для обозначения списков над А.[1]

Эквивалентные определения

В категории с конечным объектом 1 двоичный побочные продукты (обозначается +), и бинарные произведения (обозначается ×), объект списка над А можно определить как начальная алгебра из эндофунктор действует на объекты Икс ↦ 1 + (А × Икс) и стрелки ж ↦ [id1,<я быА, ж〉].[2]

Примеры

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

Характеристики

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

Предмет L1 (списки над конечным объектом) обладает универсальным свойством объект натурального числа. В любой категории со списками можно определить длина списка LА быть уникальным морфизмом л : LА → L1 что заставляет коммутировать следующую диаграмму:[3]

Коммутативная диаграмма, выражающая уравнения в определении длины объекта списка

Рекомендации

  1. ^ Джонстон 2002, A2.5.15.
  2. ^ Филип Вадлер: Рекурсивные типы бесплатно! Университет Глазго, июль 1998 г. Проект.
  3. ^ Джонстон 2002, п. 117.
  • Джонстон, Питер Т. (2002). Эскизы слона: сборник теории топосов. Оксфорд: Издательство Оксфордского университета. ISBN  0198534256. OCLC  50164783.

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