Тип семейства
Концепция в информатике

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

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

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

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

Вариации

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

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

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

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

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

класс ArrayElem e где данные Массив e индекс :: Массив e -> Int -> e

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

экземпляр ArrayElem Bool , где данные Array Bool = BoolArray BitVector индекс ( BoolArray ar ) i = indexBitVector ar i экземпляр ArrayElem Int , где данные Array Int = IntArray UIntArr индекс ( IntArray ar ) i = indexUIntArr ar i экземпляр ( ArrayElem a , ArrayElem b ) => ArrayElem ( a , b ) где данные Array ( a , b ) = PairArray ( Array a ) ( Array b ) индекс ( PairArray ar br ) = ( index ar i , index br i )

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

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

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

класс Собирает c где тип Elem c пустой :: c вставка :: Elem c - > c - > c toList :: c - > [ Elem c ] экземпляр Собирает [ e ] где тип Elem [ e ] = e пустой = [ ] вставка = ( : ) toList = id экземпляр Ord e = > Собирает ( Set.Set e ) где тип Elem ( Set.Set e ) = e пустой = Set.empty вставка = Set.insert toList = Set.toList​​​​​

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

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

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

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

Ссылки

  1. ^ ab Киселёв, Олег; Пейтон Джонс, Саймон; Шан, Чунг-Чи (2010). «Развлечения с функциями типа» (PDF) .
  2. ^ abc Чакраварти, Мануэль MT; Келлер, Габриэль ; Пейтон Джонс, Саймон; Марлоу, Саймон (2005). «Ассоциированные типы с классом». Труды 32-го ежегодного симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . ACM Press: 1–13.
  3. ^ "Функции типов, семейства типов и ассоциированные типы в GHC - Генеральный план". Апрель 2019 г. Получено 4 апреля 2019 г.
  4. ^ Wehr, Stefan; Chakravarty, Manuel MT (2008). "Модули ML и классы типов Haskell: конструктивное сравнение". Труды Шестого Азиатского симпозиума по языкам и системам программирования . Конспект лекций по информатике. 5356. Springer-Verlag: 188–204. doi :10.1007/978-3-540-89330-1_14. ISBN 978-3-540-89329-5.
  5. ^ «Связанные элементы — Справочник по Rust». Январь 2024 г.
  6. ^ "A Tour of Scala: Abstract Types" . Получено 23 февраля 2013 г. .
  7. ^ abcd Чакраварти, Мануэль MT; Келлер, Габриэль ; Пейтон Джонс, Саймон (2005). "Синонимы ассоциированных типов". Труды десятой международной конференции ACM SIGPLAN по функциональному программированию . ACM Press. стр. 241–253. doi :10.1145/1086365.1086397. ISBN 1595930647. S2CID  16406612.{{cite book}}: CS1 maint: дата и год ( ссылка )
  8. ^ "Семейства типов (TF) против функциональных зависимостей (FD)" . Получено 4 апреля 2019 г.
  • Документация Haskell Wiki по использованию семейств типов в GHC
Получено с "https://en.wikipedia.org/w/index.php?title=Type_family&oldid=1225549405"