Тип семьи - Type family

Эта статья посвящена ассоциации типов данных в информатике. О сроке набора см. Шрифт. Для биологического термина см. тип (биология).

В Информатика, а тип семьи соратники типы данных с другим типы данных, используя уровень типа функция определяется открытой коллекцией допустимых экземпляров типов ввода и соответствующих типов вывода.[1]

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

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

Языки программирования с поддержкой семейств типов или аналогичных функций включают Haskell (с расширением общего языка),[3] Стандартный ML (через свою модульную систему),[4] Scala (под названием «абстрактные типы»),[5] и C ++ (посредством использования typedefs в шаблонах).[6]

Вариации

В ТипСемьи расширение в Компилятор Glasgow Haskell поддерживает оба семейства синонимов типа и семейства данных. Семейства синонимов типов являются более гибкой (но более сложной для проверки типов) формой, допускающей типы в codomain функции типа быть любого типа с соответствующим своего рода.[6] Семейства данных, с другой стороны, ограничивают кодомен, требуя, чтобы каждый экземпляр определял новый конструктор типов для результата функции. Это гарантирует, что функция инъективный, позволяя контекстам клиентов деконструировать семейство типов и получить исходный тип аргумента.[1]

Мотивация и примеры

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

Самооптимизирующиеся абстрактные типы данных

Одной из первоначальных мотиваций введения связанных типов было разрешение абстрактные типы данных быть параметризованный по типу контента, так что структура данных реализация абстрактного типа варьируется "самооптимизирующимся" способом.[2] Нормальный алгебраический тип данных параметры могут описывать только структуры данных, которые ведут себя одинаково по отношению ко всем типам аргументов. Однако связанные типы могут описывать семейство структур данных, которые имеют единый интерфейс, но различаются по реализации в соответствии с одним или несколькими параметрами типа. Например,[2] используя нотацию связанных типов Haskell, мы можем объявить класс типа допустимого множество типы элементов со связанным семейством данных, представляющим массив этого типа элемента:

учебный класс ArrayElem е куда    данные Множество е    индекс :: Множество е -> Int -> е

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

пример ArrayElem Bool куда    данные Множество Bool = BoolArray BitVector    индекс (BoolArray ар) я = indexBitVector ар япример ArrayElem Int куда    данные Множество Int = IntArray UIntArr    индекс (IntArray ар) я = indexUIntArr ар япример (ArrayElem а, ArrayElem б) => ArrayElem (а, б) куда    данные Множество (а, б) = PairArray (Множество а) (Множество б)    индекс (PairArray ар br) = (индекс ар я, индекс br я)

Согласно этим определениям, когда клиент обращается к Массив (Int, Bool), реализация автоматически выбирается с использованием определенных экземпляров.

Класс для коллекций

Обращаясь к предыдущему примеру, мы также можем использовать семейства типов для определения класса для типов коллекций, где функция типа отображает каждый тип коллекции в соответствующий тип элемента:[6]

учебный класс Собирает c куда    тип Elem c    пустой :: c    вставлять :: Elem c -> c -> c    составлять список :: c -> [Elem c]пример Собирает [е] куда    тип Elem [е] = е    пустой = []    вставлять = (:)    составлять список = я быпример Ord е => Собирает (Набор.Набор е) куда    тип Elem (Набор.Набор е) = е    пустой = Набор.пустой    вставлять = Набор.вставлять    составлять список = Набор.составлять список

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

Сравнение с функциональными зависимостями

Функциональные зависимости - еще одна функция системы типов, которая используется аналогично связанным типам. В то время как связанный тип добавляет функцию именованного типа, сопоставляющую параметры класса включающего типа с другим типом, функциональная зависимость перечисляет тип результата как другой параметр класса типа и добавляет ограничение между параметрами типа (например, параметр а однозначно определяет параметр б", написано а -> б). Наиболее распространенные варианты использования функциональных зависимостей можно напрямую преобразовать в связанные типы и наоборот.[6]

Считается, что типовые семейства обычно легче проверять, чем функциональные зависимости. Еще одно преимущество связанных типов перед функциональными зависимостями состоит в том, что последние требуют, чтобы клиенты, использующие класс типа, указали все зависимые типы в своих контекстах, включая те, которые они не используют; так как связанные типы этого не требуют, добавление другого связанного типа в класс требует обновления только экземпляров класса, в то время как клиенты могут оставаться неизменными. Основные преимущества функциональных зависимостей перед семейством типов заключаются в их дополнительной гибкости в обработке нескольких необычных случаев.[7]

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

  1. ^ а б Киселев Олег; Пейтон Джонс, Саймон; Шан, Чжун-чжи (2010). «Развлечения с функциями типов» (PDF).
  2. ^ а б c Чакраварти, Мануэль М. Т .; Келлер, Габриэле; Пейтон Джонс, Саймон; Марлоу, Саймон (2005). «Связанные типы с классом». Материалы 32-го ежегодного симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования. ACM Нажмите: 1–13.
  3. ^ «Функции типов, семейства типов и связанные типы в GHC - Генеральный план». Получено 4 апреля 2019.
  4. ^ Вер, Стефан; Чакраварти, Мануэль М. Т. (2008). «Модули машинного обучения и классы типов Haskell: конструктивное сравнение». Материалы Шестого Азиатского симпозиума по языкам и системам программирования. Springer-Verlag.
  5. ^ «Путешествие по Scala: абстрактные типы». Получено 23 февраля 2013.
  6. ^ а б c d Чакраварти, Мануэль М. Т .; Келлер, Габриэле; Пейтон Джонс, Саймон (2005). «Синонимы ассоциированного типа». Материалы Десятой Международной конференции ACM SIGPLAN по функциональному программированию. ACM Press: 241–253.
  7. ^ «Семейства типов (TF) против функциональных зависимостей (FD)». Получено 4 апреля 2019.

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