Типовой класс - Type class

Эта статья о системах полиморфного типа в информатике. Для математического класса порядковых типов заданной мощности см. Глоссарий теории множеств § T.
Не путать с класс (компьютерное программирование).

В Информатика, а тип класс это система типов конструкция, поддерживающая специальный полиморфизм. Это достигается путем добавления ограничений на тип переменных в параметрически полиморфный типы. Такое ограничение обычно включает класс типа Т и переменная типа а, и означает, что а может быть создан только для типа, члены которого поддерживают перегруженные операции, связанные с Т.

Типовые классы были впервые реализованы в Язык программирования Haskell после первого предложения Филип Вадлер и Стивен Блотт как расширение "eqtypes" в Стандартный ML,[1][2] и изначально задумывались как способ реализации перегруженные арифметические операторы и операторы равенства принципиальным образом.[3][4]В отличие от «eqtypes» Standard ML, перегрузка оператора равенства посредством использования классов типов в Haskell не требует значительных изменений внешнего интерфейса компилятора или базовой системы типов.[5]

С момента их создания было обнаружено множество других приложений классов типов.

Обзор

Классы типов определяются путем указания набора имен функций или констант вместе с соответствующими типами, которые должны существовать для каждого типа, принадлежащего этому классу. В Haskell типы можно параметризовать; типовой класс Уравнение предназначенные для содержания типов, допускающих равенство, будут объявлены следующим образом:

учебный класс Уравнение а куда  (==) :: а -> а -> Bool  (/=) :: а -> а -> Bool

куда а является одним из экземпляров класса типа Уравнение, и а определяет сигнатуры функций для 2 функций (функции равенства и неравенства), каждая из которых принимает 2 аргумента типа а и верните логическое значение.

Переменная типа а имеет своего рода (также известный как Тип в последнем GHC релиз),[6] это означает, что вид Уравнение является

Уравнение :: Тип -> Ограничение

Объявление может быть прочитано как указание типа а принадлежит к классу типов Уравнение если есть функции с именем (==), и (/=), соответствующих типов, определенных на нем ". Затем программист может определить функцию элем (который определяет, находится ли элемент в списке) следующим образом:

элем :: Уравнение а => а -> [а] -> Boolэлем у []     = Ложьэлем у (Икс:хз) = (Икс == у) || элем у хз

Функция элем имеет тип a -> [a] -> Bool с контекстом Уравнение а, что ограничивает типы, которые а может простираться до тех а которые принадлежат Уравнение тип класс. (Примечание: Haskell => можно назвать «ограничением класса».)

Программист может сделать любой тип т член данного класса типа C используя объявление экземпляра который определяет реализации всех Cметоды для конкретного типа т. Например, если программист определяет новый тип данных т, они могут затем сделать этот новый тип экземпляром Уравнение путем предоставления функции равенства значений типа т любым способом, который они считают нужным. Как только они это сделают, они могут использовать функцию элем на [т], то есть списки элементов типа т.

Обратите внимание, что классы типов отличаются от классы в объектно-ориентированных языках программирования. Особенно, Уравнение не тип: нет такой вещи, как ценить типа Уравнение.

Классы типов тесно связаны с параметрическим полиморфизмом. Например, обратите внимание, что тип элем как указано выше, будет параметрически полиморфным типом a -> [a] -> Bool если бы не ограничение класса типа "Уравнение а =>".

Высокодородный полиморфизм

Класс типа не должен принимать переменную типа своего рода Тип но можно взять любой. Эти классы типов с более высокими типами иногда называют классами конструкторов (упомянутые конструкторы являются конструкторами типов, такими как Может быть, а не конструкторы данных, такие как Только). Примером может служить Монада учебный класс:

учебный класс Монада м куда  возвращаться :: а -> м а  (>>=)  :: м а -> (а -> м б) -> м б

Тот факт, что m применяется к переменной типа, указывает, что она имеет вид Тип -> Тип, т.е. он принимает тип и возвращает тип, вид Монада таким образом:

Монада :: (Тип -> Тип) -> Ограничение

Классы многопараметрических типов

Классы типов допускают несколько параметров типа, поэтому классы типов можно рассматривать как отношения между типами.[7] Например, в GHC стандартная библиотека, класс IArray выражает общий неизменяемый интерфейс массива. В этом классе ограничение класса типа IArray a e Значит это а - это тип массива, содержащий элементы типа е. (Это ограничение полиморфизма используется для реализации распакованный типы массивов, например.)

Нравиться мультиметоды[нужна цитата ]классы типов с несколькими параметрами поддерживают вызов различных реализаций метода в зависимости от типов нескольких аргументов и действительно возвращаемых типов. Классы с несколькими параметрами не требуют поиска метода для вызова при каждом вызове во время выполнения;[8]:минута 25:12 скорее вызываемый метод сначала компилируется и сохраняется в словаре экземпляра класса типа, как и в случае с классами типов с одним параметром.

Код Haskell, использующий классы типов с несколькими параметрами, непереносим, ​​поскольку эта возможность не является частью стандарта Haskell 98. Популярные реализации Haskell, GHC и Объятия, поддерживают классы с несколькими параметрами.

Функциональные зависимости

В Haskell классы типов были усовершенствованы, чтобы позволить программисту объявлять функциональные зависимости между параметрами типа - концепция вдохновлен теорией реляционных баз данных.[9][10] То есть программист может утверждать, что данное присвоение некоторого подмножества параметров типа однозначно определяет остальные параметры типа. Например, генерал монады м которые несут параметр состояния типа s удовлетворить ограничение класса типа Monad.State s m. В этом ограничении есть функциональная зависимость м -> с. Это означает, что для данной монады м типового класса Monad.State, тип состояния, доступный из м определяется однозначно. Это помогает компилятору в вывод типа, а также помощь программисту в типо-ориентированное программирование.

Саймон Пейтон-Джонс возражает против введения функциональных зависимостей в Haskell по причине сложности.[11]

Классы типов и неявные параметры

Классы типов и неявные параметры очень похожи по своей природе, хотя и не совсем одинаковы. Полиморфная функция с ограничением класса типа, например:

сумма :: Num а => [а] -> а

можно интуитивно рассматривать как функцию, которая неявно принимает экземпляр Num:

сумма_ :: Num_ а -> [а] -> а

Экземпляр Num_ a по сути, это запись, содержащая определение экземпляра Num a. (Фактически, именно так классы типов реализуются под капотом компилятора Glasgow Haskell.)

Однако есть принципиальное отличие: неявные параметры больше гибкий - вы можете передавать разные экземпляры Num Int. Напротив, классы типов применяют так называемые согласованность свойство, которое требует, чтобы был только один уникальный выбор экземпляра для любого данного типа. Свойство coherence делает классы типов в некоторой степени антимодульными, поэтому настоятельно не рекомендуется использовать бесхозные экземпляры (экземпляры, которые определены в модуле, который не содержит ни класс, ни интересующий тип). С другой стороны, согласованность добавляет языку дополнительный уровень безопасности, обеспечивая программисту гарантию того, что две непересекающиеся части одного и того же кода будут совместно использовать один и тот же экземпляр.[12]

Например, заказанный набор (типа Установить) требует общий заказ на элементах (типа а) для того, чтобы функционировать. Об этом может свидетельствовать ограничение Ord a, который определяет оператор сравнения для элементов. Однако существует множество способов навести тотальный порядок. Поскольку алгоритмы набора обычно нетерпимы к изменениям в порядке после создания набора, передача несовместимого экземпляра Ord a к функциям, которые работают на устройстве, может привести к неверным результатам (или сбоям). Таким образом, обеспечение согласованности Ord a в этом конкретном сценарии имеет решающее значение.

Экземпляры (или "словари") в Scala классы типов - это просто обычные значения в языке, а не совершенно отдельный вид сущности.[13][14] Хотя эти экземпляры по умолчанию предоставляются путем нахождения подходящих экземпляров в области видимости для использования в качестве неявных фактических параметров для явно объявленных неявных формальных параметров, тот факт, что они являются обычными значениями, означает, что они могут быть предоставлены явно для устранения неоднозначности. В результате классы типов Scala не удовлетворяют свойству согласованности и фактически являются синтаксическим сахаром для неявных параметров.

Это пример из книги Кошек. [15] документация:

// Класс типа для текстового представлениячерта Показать[А] {  def Показать(ж: А): Нить}// Полиморфная функция, которая работает только при неявном // экземпляр Show [A] доступенdef бревно[А](а: А)(скрытый s: Показать[А]) = println(s.Показать(а))// Экземпляр для Stringскрытый вал stringShow = новый Показать[Нить] {  def Показать(s: Нить) = s}// Параметр stringShow был вставлен компилятором.Scala> бревно("строка")а нить

Coq (версия 8.2 и новее) также поддерживает классы типов путем вывода соответствующих экземпляров.[16] Последние версии Агда 2 также предоставляют аналогичную функцию, называемую «аргументами экземпляра».[17]

Другие подходы к перегрузке операторов

В Стандартный ML, механизм «типов равенства» примерно соответствует классу встроенных типов Haskell Уравнение, но все операторы равенства выводятся компилятором автоматически. Контроль программиста над процессом ограничивается указанием того, какие компоненты типа в структуре являются типами равенства, а какие переменные типа в диапазоне полиморфных типов над типами равенства.

SML и OCaml модули и функторы могут играть роль, аналогичную роли классов типов Haskell, основное отличие заключается в роли вывода типов, что делает классы типов подходящими для для этого случая полиморфизм.[18]Объектно-ориентированное подмножество OCaml это еще один подход, который несколько сравним с подходом классов типов.

Связанные понятия

Аналогичное понятие для перегруженных данных (реализовано в GHC ) принадлежит тип семьи.[19]

В Чистый классы типов похожи на Haskell, но имеют немного другой синтаксис.

Ржавчина поддерживает черты, которые представляют собой ограниченную форму классов типов с согласованностью.[20]

Меркурий имеет классы типов, хотя они не совсем такие, как в Haskell.[требуется дальнейшее объяснение ]

В Scala, классы типов - это идиома программирования который может быть реализован с помощью существующих языковых функций, таких как неявные параметры, а не отдельной языковой функции как таковой. Благодаря тому, как они реализованы в Scala, можно явно указать, какой экземпляр класса типа использовать для типа в конкретном месте кода в случае двусмысленности. Однако это не обязательно является преимуществом, поскольку экземпляры классов неоднозначного типа могут быть подвержены ошибкам.

Помощник доказательства Coq также поддерживает классы типов в последних версиях. В отличие от обычных языков программирования, в Coq любые законы класса типов (например, законы монад), которые изложены в определении класса типа, должны быть математически подтверждены для каждого экземпляра класса типа перед их использованием.

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

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

  1. ^ Моррис, Джон (2013). «Классы типов и цепочки экземпляров» (PDF).
  2. ^ Вадлер, Филипп (октябрь 1988 г.). "Как сделать специальный полиморфизм менее случайным".
  3. ^ Каес, Стефан (март 1988 г.). «Параметрическая перегрузка в полиморфных языках программирования». Proc. 2-й Европейский симпозиум по языкам программирования. Дои:10.1007/3-540-19027-9_9.
  4. ^ Вадлер, Филипп; Стивен Блотт (январь 1989 г.). "Как сделать специальный полиморфизм менее случайным". Proc. 16-й симпозиум ACM по принципам языков программирования.
  5. ^ Аппель, Эндрю; Дэвид Маккуин (июнь 1991 г.). "Стандартный ML Нью-Джерси". Proc. 3-й Международный симпозиум по реализации языков программирования и логическому программированию.
  6. ^ Тип из Data.Kind появился в версии 8 Компилятор Glasgow Haskell
  7. ^ Haskell ' страница MultiParamTypeClasses.
  8. ^ В GHC ядро ​​C использует сигнатуры типа System F от Girard & Reynold для определения типизированного случая для обработки на этапах оптимизации. - Саймон Пейтон-Джонс "В ядро ​​- сжатие Haskell до девяти конструкторов » Конференция пользователей Erlang, 14 сентября 2016 г.
  9. ^ Марк Джонс. Классы типов с функциональными зависимостями. Из Proc. 9-й Европейский симпозиум по программированию. Март 2000 г.
  10. ^ Haskell ' страница Функциональные зависимости.
  11. ^ http://www.haskell.org/pipermail/haskell-prime/2006-Feb February/000289.html
  12. ^ Эдвард Кметт, Типовые классы против мира, Встреча сообщества Boston Haskell.
  13. ^ Оливейра, Бруно; Адриан Мурс; Мартин Одерский (2010). «Классы типов как объекты и следствия» (PDF). OOPSLA.
  14. ^ "Руководство по Scala для неофита, часть 12: Типовые классы - Дэниел Вестхайд".
  15. ^ typelevel.org, Scala Cats
  16. ^ Нежное введение в классы типов и отношения в Coq
  17. ^ "Классы типов моделирования с аргументами экземпляра ".
  18. ^ Дрейер, Дерек; Роберт Харпер; Мануэль М.Т. Чакраварти (апрель 2006 г.). «Классы модульного типа». Цитировать журнал требует | журнал = (помощь)
  19. ^ "GHC / Семейства типов - HaskellWiki".
  20. ^ «Специализация, согласованность и эволюция API · Аарон Турон».

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