GHC.Generics

Авторские права	(c) Университет Утрехта 2010-2011, Оксфордский университет 2012-2013
Лицензия	см. libraries/base/LICENSE
Поддерживающий	libraries@haskell.org
Устойчивость	внутренняя
Переносимость	непереносимая
Безопасный Haskell	Достоверный
Язык	Haskell2010

Введение

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

Представимые типы собираются в классе Generic, который определяет ассоциированный тип Rep и функции преобразования from и to. Как правило, вы не будете определять экземпляры Generic вручную, но заставите компилятор сгенерировать их для вас.

Представление типов данных

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

Давайте сначала рассмотрим пример:

data Tree a = Leaf a | Node (Tree a) (Tree a)
  deriving Generic

Вышеприведенное объявление (которое требует прагмы языка DeriveGeneric) приводит к следующему представлению:

instance Generic (Tree a) where
  type Rep (Tree a) =
    D1 D1Tree
      (C1 C1_0Tree
         (S1 NoSelector (Par0 a))
       :+:
       C1 C1_1Tree
         (S1 NoSelector (Rec0 (Tree a))
          :*:
          S1 NoSelector (Rec0 (Tree a))))
  ...

Подсказка: Вы можете получить информацию о генерируемом коде из GHC, передав флаг -ddump-deriv. В GHCi вы можете развернуть семейство типов, например, Rep, с помощью команды :kind!

Производные и базовые типы представления

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

Отдельные поля конструкторов: K1

Конструкторы типов Par0 и Rec0 являются вариантами K1

type Par0 = K1 P
type Rec0 = K1 R

Здесь P и R — это снова прокси-типы, не имеющие связанных значений.

Метаинформация: M1

Конструкторы типов S1, C1 и D1 — это все варианты M1

type S1 = M1 S
type C1 = M1 C
type D1 = M1 D

Типы S, C и D опять же являются прокси-типами, используемыми только для создания нескольких вариантов M1

Дополнительные конструкторы типов обобщенного представления

Помимо K1, M1, :+: и :*: существует несколько других конструкторов типов, которые встречаются в представлениях других типов данных.

Пустые типы данных: V1

Для пустых типов данных используется представление V1. Например,

data Empty deriving Generic

дает

instance Generic Empty where
  type Rep Empty = D1 D1Empty V1

Конструкторы без полей: U1

Если у конструктора нет аргументов, то используется представление U1. Например, представление Bool — это

instance Generic Bool where
  type Rep Bool =
    D1 D1Bool
      (C1 C1_0Bool U1 :+: C1 C1_1Bool U1)

Представление типов с множеством конструкторов или полей

Поскольку :+: и :*: — это просто бинарные операторы, можно спросить, что произойдёт, если тип данных имеет более двух конструкторов или конструктор с более чем двумя полями. Ответ прост: операторы используются несколько раз, чтобы комбинировать все конструкторы и поля по мере необходимости. Однако пользователи /не должны полагаться на определённую стратегию вложения/ для :+: и :*:. Компилятор свободен выбирать любое вложение, которое ему нравится. (На практике текущая реализация пытается создать более или менее сбалансированное вложение, так что обход структуры типа данных от корня до конкретного компонента можно выполнить за логарифмическое, а не линейное время.)

Определение функций, обобщенных по типу данных

Функция, обобщенная по типу данных, состоит из двух частей:

1. Обобщенные экземпляры для функции, реализующие её для большинства конструкторов типов представления, представленных выше.
2. Оборачивающий, который для любого типа данных, который находится в Generic, выполняет преобразование между исходным значением и его представлением на основе Rep, а затем вызывает обобщенные экземпляры.

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

encode :: Generic a => a -> [Bool]

где мы используем Bool в качестве нашего типа данных для битов.

Для первой части мы определим класс Encode'. Возможно, неожиданно, что этот класс параметризован конструктором типа f с типом * -> *. Это технический момент: все конструкторы типов представления работают со значением * -> * в качестве базового типа. Но аргумент типа никогда не используется. Это может быть изменено в будущем. Класс имеет один метод, и мы используем тип, который мы хотим для нашей конечной функции, но заменяем вхождения обобщенного аргумента типа a на f p (где p — любой аргумент; он не будет использоваться).

class Encode' f where
  encode' :: f p -> [Bool]

С целью сделать encode работающей с Tree и другими типами данных, мы теперь определяем экземпляры для конструкторов типов представления V1, U1, :+:, :*:, K1 и M1

Определение типов обобщенного представления

Для этого нам нужны фактические определения этих типов:

data    V1        p                       -- lifted version of Empty
data    U1        p = U1                  -- lifted version of ()
data    (:+:) f g p = L1 (f p) | R1 (g p) -- lifted version of Either
data    (:*:) f g p = (f p) :*: (g p)     -- lifted version of (,)
newtype K1    i c p = K1 { unK1 :: c }    -- a container for a c
newtype M1  i t f p = M1 { unM1 :: f p }  -- a wrapper

Итак, U1 — это просто тип единицы, :+: — это просто двоичный выбор, подобный Either, :*: — это двоичная пара, подобная конструктору пар (,), а K1 — это значение определенного типа c, и M1 оборачивает значение обобщенного аргумента типа, что в поднятом мире является f p (где нас не интересует p).

Обобщенные экземпляры

Экземпляр для V1 немного нелепый (но и редко используется):

instance Encode' V1 where
  encode' x = undefined

Нет значений типа V1 p для передачи (кроме undefined), поэтому это фактически невозможно. Можно спросить, зачем вообще полезно определять экземпляр для V1 в этом случае? Ну, пустой тип может использоваться как аргумент для непустого типа, и вы всё ещё можете захотеть закодировать полученный тип. Как пример, рассмотрим [Empty], который не является пустым типом, но содержит только пустой список. Экземпляр V1 гарантирует, что мы можем вызвать обобщенную функцию для таких типов.

Существует ровно одно значение типа U1, поэтому его кодирование не требует знаний, и мы можем использовать ноль битов:

instance Encode' U1 where
  encode' U1 = []

В случае :+: мы получаем False или True в зависимости от того, находится ли конструктор предоставленного значения слева или справа:

instance (Encode' f, Encode' g) => Encode' (f :+: g) where
  encode' (L1 x) = False : encode' x
  encode' (R1 x) = True  : encode' x

В случае :*: мы добавляем кодирования двух подкомпонентов:

instance (Encode' f, Encode' g) => Encode' (f :*: g) where
  encode' (x :*: y) = encode' x ++ encode' y

Случай для K1 довольно интересный. Здесь мы рекурсивно вызываем конечную функцию encode, которую ещё нужно определить. Мы будем использовать другой класс типов Encode для этой функции:

instance (Encode c) => Encode' (K1 i c) where
  encode' (K1 x) = encode x

Обратите внимание, как Par0 и Rec0 оба сопоставляются с K1, что позволяет нам определить здесь унифицированный экземпляр.

Аналогичным образом, мы можем определить унифицированный экземпляр для M1, поскольку мы полностью игнорируем всю метаинформацию:

instance (Encode' f) => Encode' (M1 i t f) where
  encode' (M1 x) = encode' x

В отличие от K1, экземпляр для M1 ссылается на encode', а не на encode.

Обертка и обобщенное значение по умолчанию

Теперь мы определяем класс Encode для фактической функции encode:

class Encode a where
  encode :: a -> [Bool]
  default encode :: (Generic a) => a -> [Bool]
  encode x = encode' (from x)

Приходящее значение x преобразуется с помощью from, затем мы выполняем переадресацию к универсальным экземплярам с помощью encode'. Мы используем это как стандартное определение для encode. Нам нужна сигнатура «стандартного кодирования», потому что обычные стандартные методы Haskell не должны вводить дополнительные ограничения класса, но наш универсальный стандарт — делает.

Определение конкретного экземпляра теперь так же просто, как сказать

instance (Encode a) => Encode (Tree a)

Опускание универсальных экземпляров

Не всегда требуется предоставлять экземпляры для всех типов универсального представления, но пропуск экземпляров ограничивает набор типов данных, для которых будут работать функции:

• Если не указан экземпляр :+:, функция может по-прежнему работать с пустыми типами данных или типами данных, у которых есть единственный конструктор, но не будет работать с типами данных, имеющими более одного конструктора.
• Если не указан экземпляр :*:, функция может по-прежнему работать с типами данных, где каждый конструктор имеет только ноль или один параметр, в частности, для типов перечисления.
• Если не указан экземпляр K1, функция может по-прежнему работать с типами перечисления, где ни один конструктор не имеет параметров.
• Если не указан экземпляр V1, функция может по-прежнему работать с любым непустым типом данных.
• Если не указан экземпляр U1, функция может по-прежнему работать с любым типом данных, где каждый конструктор имеет по крайней мере один параметр.

Экземпляр M1 всегда требуется (но он может просто игнорировать метаинформацию, как в случае с encode выше).

Универсальные классы конструкторов

Определенные выше функции, работающие с типами данных, подходят для большого класса типов данных, включая параметризованные типы данных. (Мы использовали Tree в качестве примера выше, который относится к типу * -> *.) Однако класс Generic охватывает типы с видом *, и поэтому полученные универсальные функции (например, encode) должны быть параметризованы универсальным аргументом типа с видом *.

Что делать, если нужно определить универсальные классы, которые охватывают конструкторы типов (такие как Functor, Traversable или Foldable)?

Класс Generic1

Подобно Generic, существует класс Generic1, который определяет представление Rep1 и функции преобразования from1 и to1, только Generic1 охватывает типы с видом * -> * Класс Generic1 также выводим.

Представление Rep1 немного отличается от Rep. Давайте рассмотрим Tree ещё раз в качестве примера:

data Tree a = Leaf a | Node (Tree a) (Tree a)
  deriving Generic1

Вышеуказанное объявление приводит к генерации следующего представления:

instance Generic1 Tree where type Rep1 Tree = D1 D1Tree (C1 C1_0Tree (S1 NoSelector Par1) :+: C1 C1_1Tree (S1 NoSelector (Rec1 Tree) :*: S1 NoSelector (Rec1 Tree))) ...

Представление повторно использует D1, C1, S1 (и, следовательно, M1 ), а также :+: и :*: из Rep. (Эта возможность повторного использования является причиной того, что мы используем фиктивный аргумент типа для типов с видом kind-* , но и без того участвуют достаточно разные имена, чтобы не дублировать каждый из них.)

Отличие в том, что мы теперь используем Par1 для ссылки на параметр (а этот параметр, который раньше был a ), нигде не упоминается по имени; и мы используем Rec1 для ссылки на рекурсивное использование Tree a.

Представление типов * -> *

В отличие от Par0 и Rec0, конструкторы типов Par1 и Rec1 не отображаются на K1. Они определяются непосредственно, как показано ниже:

newtype Par1   p = Par1 { unPar1 ::   p } -- gives access to parameter p
newtype Rec1 f p = Rec1 { unRec1 :: f p } -- a wrapper

В Par1 параметр p используется впервые, тогда как Rec1 просто оборачивает применение f к p.

Обратите внимание, что K1 (в виде Rec0 ) может все еще встречаться в представлении Rep1 , а именно, когда тип данных имеет параметр, который не упоминает параметр.

Объявление

data WithInt a = WithInt Int a
  deriving Generic1

дает

class Rep1 WithInt where
  type Rep1 WithInt =
    D1 D1WithInt
      (C1 C1_0WithInt
        (S1 NoSelector (Rec0 Int)
         :*:
         S1 NoSelector Par1))

Если параметр a появляется под композицией других конструкторов типов, то представление также включает композицию:

data Rose a = Fork a [Rose a]

дает

class Rep1 Rose where
  type Rep1 Rose =
    D1 D1Rose
      (C1 C1_0Rose
        (S1 NoSelector Par1
         :*:
         S1 NoSelector ([] :.: Rec1 Rose)

где

newtype (:.:) f g p = Comp1 { unComp1 :: f (g p) }

Универсальные типы представления

data V1 p Source

Пустое значение: используется для типов данных без конструкторов

data U1 p Source

Единица: используется для конструкторов без аргументов

newtype Par1 p Source

Используется для маркировки вхождений параметра

newtype Rec1 f p Source

Рекурсивные вызовы вида * -> *

newtype M1 i c f p Источник

Метаинформация (имена конструкторов и т. д.)

data (f :+: g) p infixr 5 Источник

Суммы: кодирование выбора между конструкторами

data (f :*: g) p infixr 6 Источник

Произведения: кодирование нескольких аргументов конструкторов

newtype (f :.: g) p infixr 7 Источник

Композиция функторов

Синонимы для удобства

type Rec0 = K1 R Источник

Синоним типа для кодирования рекурсии (типа *)

type Par0 = K1 P Источник

Синоним типа для кодирования параметров (кроме последнего)

data R Источник

Тег для K1: рекурсия (типа *)

data P Источник

Тег для K1: параметры (кроме последнего)

type D1 = M1 D Источник

Синоним типа для кодирования метаинформации для типов данных

type C1 = M1 C Источник

Синоним типа для кодирования метаинформации для конструкторов

type S1 = M1 S Источник

Синоним типа для кодирования метаинформации для селекторов записей

data D Источник

Тег для M1: тип данных

data C Source

Метка для M1: конструктор

data S Source

Метка для M1: селектор записи

Метаинформация

class Datatype d where Source

Класс для типов данных, представляющих типы данных

class Constructor c where Source

Класс для типов данных, представляющих конструкторы данных

class Selector s where Source

Класс для типов данных, представляющих записи

data NoSelector Source

Используется для полей конструктора без имени

data Fixity Source

Тип данных для представления фиксированности конструктора. Объявление infix | напрямую соответствует применению Infix.

data Associativity Source

Тип данных для представления ассоциативности конструктора

data Arity Source

Тип данных для представления арности кортежа.

prec :: Fixity -> Int Source

Получить приоритет значения фиксированности.

Обобщенные классы типов

class Generic a where Source

Типы, представляемые с типом * . Этот класс может быть выведен в GHC с флагом DeriveGeneric.

class Generic1 f where Source

Представимые типы рода * -> *. Этот класс выводим в GHC с флагом DeriveGeneric.