Jump to content

Тип семейства

В информатике семейство типов связывает типы данных с другими типами данных уровня типа, , используя функцию определяемую открытой коллекцией допустимых экземпляров входных типов и соответствующих выходных типов. [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]

  1. ^ Jump up to: а б Киселев Олег; Пейтон Джонс, Саймон; Шан, Чунг-чи (2010). «Развлечение с функциями типов» (PDF) .
  2. ^ Jump up to: а б с Чакраварти, Мануэль М.Т.; Келлер, Габриэле ; Пейтон Джонс, Саймон; Марлоу, Саймон (2005). «Связанные типы с классом» . Материалы 32-го ежегодного симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . ACM Пресс: 1–13.
  3. ^ «Функции типов, семейства типов и связанные типы в GHC — генеральный план» . Апрель 2019 года . Проверено 4 апреля 2019 г.
  4. ^ Вер, Стефан; Чакраварти, Мануэль М.Т. (2008). «Модули ML и классы типов Haskell: конструктивное сравнение» . Материалы шестого АЗИАТСКОГО симпозиума по языкам и системам программирования . Конспекты лекций по информатике. 5356 . Спрингер-Верлаг: 188–204. дои : 10.1007/978-3-540-89330-1_14 . ISBN  978-3-540-89329-5 .
  5. ^ «Связанные элементы — Ссылка на ржавчину» . Январь 2024 года.
  6. ^ «Экскурсия по Scala: абстрактные типы» . Проверено 23 февраля 2013 г.
  7. ^ Jump up to: а б с д Чакраварти, Мануэль М.Т.; Келлер, Габриэле ; Пейтон Джонс, Саймон (2005). «Синонимы ассоциированного типа» . Материалы десятой международной конференции ACM SIGPLAN по функциональному программированию . АКМ Пресс. стр. 241–253. дои : 10.1145/1086365.1086397 . ISBN  1595930647 . S2CID   16406612 . {{cite book}}: CS1 maint: дата и год ( ссылка )
  8. ^ «Семейства типов (TF) и функциональные зависимости (FD)» . Проверено 4 апреля 2019 г.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: b5fb0e50c9b92b1b2b97d36a6c8ad8d0__1716601740
URL1:https://arc.ask3.ru/arc/aa/b5/d0/b5fb0e50c9b92b1b2b97d36a6c8ad8d0.html
Заголовок, (Title) документа по адресу, URL1:
Type family - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)