Тип семейства
В информатике семейство типов связывает типы данных с другими типами данных уровня типа, , используя функцию определяемую открытой коллекцией допустимых экземпляров входных типов и соответствующих выходных типов. [1]
Семейства типов — это особенность некоторых систем типов , которая позволяет определять частичные функции между типами путем сопоставления с образцом . В этом отличие от конструкторов типов данных , которые определяют инъективные функции из всех типов определенного вида в новый набор типов, и синонимов типов (также известных как typedef ), которые определяют функции из всех типов определенного вида в другой существующий набор типов. типы, использующие один регистр.
Семейства типов и классы типов тесно связаны: обычные классы типов определяют частичные функции от типов к коллекции именованных значений путем сопоставления с образцом входных типов, тогда как семейства типов определяют частичные функции от типов к типам путем сопоставления с образцом входных типов. Фактически, во многих случаях использования семейств типов существует единственный класс типов, который логически содержит как значения, так и типы, связанные с каждым экземпляром. Семейство типов, объявленное внутри класса типов, называется ассоциированным типом . [2]
Языки программирования с поддержкой семейств типов или подобных функций включают Haskell (с общим языковым расширением), [3] Стандартное ML (через систему модулей), [4] Ржавчина , [5] Scala (под названием «абстрактные типы»), [6] и C++ (за счет использования определений типов в шаблонах). [7]
Вариации
[ редактировать ]The TypeFamilies Расширение компилятора Glasgow Haskell поддерживает как семейства синонимов типов, так и семейства данных . Семейства синонимов типов представляют собой более гибкую (но более сложную для проверки типов) форму, позволяющую типам в кодомене функции типа быть любым типом с соответствующим kind . [7] Семейства данных, с другой стороны, ограничивают кодомен, требуя, чтобы каждый экземпляр определял новый конструктор типа для результата функции. Это гарантирует, что функция является инъективной , позволяя контекстам клиентов деконструировать семейство типов и получить исходный тип аргумента. [1]
Мотивация и примеры
[ редактировать ]Семейства типов полезны для абстрагирования шаблонов, в которых повторяется общая «организация» или «структура» типов, но в каждом случае с разными конкретными типами. Типичные случаи использования включают описание абстрактных типов данных , таких как общие коллекции, или шаблонов проектирования, таких как модель-представление-контроллер .
Самооптимизирующиеся абстрактные типы данных
[ редактировать ]Одной из первоначальных причин для введения связанных типов было предоставление возможности типы данных абстрактные параметризовать по их типу контента, чтобы структура данных, реализующая абстрактный тип, изменялась «самооптимизирующимся» способом. [2] Параметры обычного алгебраического типа данных могут описывать только структуры данных, которые ведут себя одинаково по отношению ко всем типам аргументов. Однако связанные типы могут описывать семейство структур данных, которые имеют единый интерфейс, но различаются по реализации в зависимости от одного или нескольких параметров типа. Например, [2] используя нотацию связанных типов Haskell, мы можем объявить класс типов допустимых типов элементов массива со связанным семейством данных, представляющим массив этого типа элемента:
class ArrayElem e where
data Array e
index :: Array e -> Int -> e
Затем для этого класса можно определить экземпляры, которые определяют как используемую структуру данных, так и операции над структурой данных в одном месте. Для эффективности мы могли бы использовать представление упакованного битового вектора для массивов логических значений, используя при этом обычную структуру данных массива для целочисленных значений. Структура данных для массивов упорядоченных пар определяется рекурсивно как пара массивов каждого из типов элементов.
instance ArrayElem Bool where
data Array Bool = BoolArray BitVector
index (BoolArray ar) i = indexBitVector ar i
instance ArrayElem Int where
data Array Int = IntArray UIntArr
index (IntArray ar) i = indexUIntArr ar i
instance (ArrayElem a, ArrayElem b) => ArrayElem (a, b) where
data Array (a, b) = PairArray (Array a) (Array b)
index (PairArray ar br) = (index ar i, index br i)
Согласно этим определениям, когда клиент обращается к Array (Int, Bool), реализация автоматически выбирается с использованием определенных экземпляров.
Класс для коллекций
[ редактировать ]Инвертируя предыдущий пример, мы также можем использовать семейства типов для определения класса типов коллекций, где функция типа сопоставляет каждый тип коллекции соответствующему типу элемента: [7]
class Collects c where
type Elem c
empty :: c
insert :: Elem c -> c -> c
toList :: c -> [Elem c]
instance Collects [e] where
type Elem [e] = e
empty = []
insert = (:)
toList = id
instance Ord e => Collects (Set.Set e) where
type Elem (Set.Set e) = e
empty = Set.empty
insert = Set.insert
toList = Set.toList
В этом примере важно использовать семейство синонимов типов вместо семейства данных, поскольку несколько типов коллекций могут иметь один и тот же тип элемента.
Сравнение с функциональными зависимостями
[ редактировать ]Функциональные зависимости — это еще одна функция системы типов, которая используется аналогично связанным типам. В то время как связанный тип добавляет функцию именованного типа, сопоставляющую параметры включающего класса типа с другим типом, функциональная зависимость перечисляет тип результата как еще один параметр класса типа и добавляет ограничение между параметрами типа (например, «параметр a однозначно определяет параметр b ", написано a -> b). Наиболее распространенные варианты использования функциональных зависимостей можно напрямую преобразовать в связанные типы и наоборот. [7]
Считается, что семейства типов обычно легче проверять, чем функциональные зависимости. Еще одно преимущество связанных типов перед функциональными зависимостями состоит в том, что последние требуют от клиентов, использующих класс типов, указывать все зависимые типы в их контекстах, включая те, которые они не используют; поскольку связанные типы этого не требуют, добавление в класс еще одного связанного типа требует обновления только экземпляров класса, в то время как клиенты могут оставаться неизменными. Основные преимущества функциональных зависимостей перед семействами типов заключаются в дополнительной гибкости при обработке некоторых необычных случаев. [8]
Ссылки
[ редактировать ]- ^ Jump up to: а б Киселев Олег; Пейтон Джонс, Саймон; Шан, Чунг-чи (2010). «Развлечение с функциями типов» (PDF) .
- ^ Jump up to: а б с Чакраварти, Мануэль М.Т.; Келлер, Габриэле ; Пейтон Джонс, Саймон; Марлоу, Саймон (2005). «Связанные типы с классом» . Материалы 32-го ежегодного симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . ACM Пресс: 1–13.
- ^ «Функции типов, семейства типов и связанные типы в GHC — генеральный план» . Апрель 2019 года . Проверено 4 апреля 2019 г.
- ^ Вер, Стефан; Чакраварти, Мануэль М.Т. (2008). «Модули ML и классы типов Haskell: конструктивное сравнение» . Материалы шестого АЗИАТСКОГО симпозиума по языкам и системам программирования . Конспекты лекций по информатике. 5356 . Спрингер-Верлаг: 188–204. дои : 10.1007/978-3-540-89330-1_14 . ISBN 978-3-540-89329-5 .
- ^ «Связанные элементы — Ссылка на ржавчину» . Январь 2024 года.
- ^ «Экскурсия по Scala: абстрактные типы» . Проверено 23 февраля 2013 г.
- ^ Jump up to: а б с д Чакраварти, Мануэль М.Т.; Келлер, Габриэле ; Пейтон Джонс, Саймон (2005). «Синонимы ассоциированного типа» . Материалы десятой международной конференции ACM SIGPLAN по функциональному программированию . АКМ Пресс. стр. 241–253. дои : 10.1145/1086365.1086397 . ISBN 1595930647 . S2CID 16406612 .
{{cite book}}: CS1 maint: дата и год ( ссылка ) - ^ «Семейства типов (TF) и функциональные зависимости (FD)» . Проверено 4 апреля 2019 г.