Существует несколько способов выполнять обобщённое программирование с учётом типов данных, используя инфраструктуру GHC.Generics. Один из них — использовать обёртки Generically и Generically1 из GHC.Generics; экземпляры можно выводить с помощью DerivingVia:
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE DerivingStrategies #-}
{-# LANGUAGE DerivingVia #-}
import GHC.Generics
data V4 a = V4 a a a a
deriving
stock (Generic, Generic1)
deriving (Semigroup, Monoid)
via Generically (V4 a)
deriving (Functor, Applicative)
via Generically1 V4
В более старом подходе используются DeriveGeneric, DefaultSignatures и DeriveAnyClass. В нём экземпляры выводятся путём предоставления специальной обобщённой реализации в объявлении класса типов. В этом разделе кратко рассматривается, как это делается.
Поддержка обобщённого программирования в GHC позволяет определять классы с методами, для которых не требуется спецификация пользователя при создании экземпляра: тело метода автоматически выводится GHC. Это похоже на то, что происходит, например, со стандартными классами Read и Show, но теперь речь идёт о классах, определённых пользователем.
Примечание
Раньше в GHC была реализация обобщённых классов, описанных в статье «Derivable type classes» Ральфа Хинце и Саймона Пейтона Джонса (Haskell Workshop, Монреаль, сентябрь 2000 г., с. 94–105). Эти классы были удалены и заменены более общей поддержкой обобщённого программирования.
6.19.3.1. Вывод представлений
Прежде всего нам нужны обобщённые представления. Модуль GHC.Generics определяет несколько примитивных типов, используемых для представления типов данных Haskell:
-- | Unit: used for constructors without arguments
data U1 p = U1
-- | Constants, additional parameters and recursion of kind Type
newtype K1 i c p = K1 { unK1 :: c }
-- | Meta-information (constructor names, etc.)
newtype M1 i c f p = M1 { unM1 :: f p }
-- | Sums: encode choice between constructors
infixr 5 :+:
data (:+:) f g p = L1 (f p) | R1 (g p)
-- | Products: encode multiple arguments to constructors
infixr 6 :*:
data (:*:) f g p = f p :*: g p
Классы Generic и Generic1 связывают определённые пользователем типы данных с их внутренним представлением в виде суммы произведений:
class Generic a where -- Encode the representation of a user datatype type Rep a :: Type -> Type -- Convert from the datatype to its representation from :: a -> (Rep a) x -- Convert from the representation to the datatype to :: (Rep a) x -> a class Generic1 (f :: k -> Type) where type Rep1 f :: k -> Type from1 :: f a -> Rep1 f a to1 :: Rep1 f a -> f a
Generic1 используется для функций, которые можно определять только для контейнеров типов, например map. Обратите внимание, что по умолчанию Generic1 охватывает типы рода Type -> Type, но если включено расширение PolyKinds, оно может охватывать типы рода k -> Type для любого рода k.
-
DeriveGeneric -
Разрешает автоматический вывод экземпляров для класса типов
Generic.
GHC может выводить экземпляры этих классов при включённом расширении DeriveGeneric; они необходимы для автоматического определения обобщённых экземпляров.
Например, для определённого пользователем типа данных деревьев
data UserTree a = Node a (UserTree a) (UserTree a) | Leaf
в модуле Main пакета с именем foo будет сгенерировано следующее представление:
instance Generic (UserTree a) where
-- Representation type
type Rep (UserTree a) =
M1 D ('MetaData "UserTree" "Main" "package-name" 'False) (
M1 C ('MetaCons "Node" 'PrefixI 'False) (
M1 S ('MetaSel 'Nothing
'NoSourceUnpackedness
'NoSourceStrictness
'DecidedLazy)
(K1 R a)
:*: M1 S ('MetaSel 'Nothing
'NoSourceUnpackedness
'NoSourceStrictness
'DecidedLazy)
(K1 R (UserTree a))
:*: M1 S ('MetaSel 'Nothing
'NoSourceUnpackedness
'NoSourceStrictness
'DecidedLazy)
(K1 R (UserTree a)))
:+: M1 C ('MetaCons "Leaf" 'PrefixI 'False) U1)
-- Conversion functions
from (Node x l r) = M1 (L1 (M1 (M1 (K1 x) :*: M1 (K1 l) :*: M1 (K1 r))))
from Leaf = M1 (R1 (M1 U1))
to (M1 (L1 (M1 (M1 (K1 x) :*: M1 (K1 l) :*: M1 (K1 r))))) = Node x l r
to (M1 (R1 (M1 U1))) = Leaf
Это представление генерируется автоматически, если к объявлению типа данных добавить предложение deriving Generic. Можно также использовать автономный вывод экземпляров.
6.19.3.2. Написание обобщённых функций
Обобщённая функция определяется созданием класса и заданием экземпляров для каждого из типов представления GHC.Generics. В качестве примера рассмотрим обобщённую сериализацию:
data Bin = O | I class GSerialize f where gput :: f a -> [Bin] instance GSerialize U1 where gput U1 = [] instance (GSerialize a, GSerialize b) => GSerialize (a :*: b) where gput (x :*: y) = gput x ++ gput y instance (GSerialize a, GSerialize b) => GSerialize (a :+: b) where gput (L1 x) = O : gput x gput (R1 x) = I : gput x instance (GSerialize a) => GSerialize (M1 i c a) where gput (M1 x) = gput x instance (Serialize a) => GSerialize (K1 i a) where gput (K1 x) = put x
Следует учитывать, что эта стратегия кодирования может быть ненадёжной при переходе между разными версиями GHC. При выводе экземпляра Generic можно выбрать любую вложенность :+: и :*:. Поэтому, если GHC выберет (a :+: b) :+: c, кодирование для a будет [O, O], для b — [O, I], а для c — [I]. Однако если GHC выберет a :+: (b :+: c), кодирование для a будет [O], для b — [I, O], а для c — [I, I]. (На практике текущая реализация старается создавать более или менее сбалансированную вложенность :+: и :*:, чтобы обход структуры типа данных от корня до конкретного компонента занимал логарифмическое, а не линейное время.)
Как правило, класс GSerialize не экспортируется, поскольку экземпляры для него имеют смысл только для типов представления.
6.19.3.3. Типы представления без подъёма
Семейство данных URec предназначено для обобщённого программирования с типами данных, имеющими определённые аргументы без подъёма. Для распространённых типов без подъёма предусмотрено шесть экземпляров:
data family URec a p
data instance URec (Ptr ()) p = UAddr { uAddr# :: Addr# }
data instance URec Char p = UChar { uChar# :: Char# }
data instance URec Double p = UDouble { uDouble# :: Double# }
data instance URec Int p = UInt { uInt# :: Int# }
data instance URec Float p = UFloat { uFloat# :: Float# }
data instance URec Word p = UWord { uWord# :: Word# }
Для удобства предусмотрено шесть синонимов типов:
type UAddr = URec (Ptr ()) type UChar = URec Char type UDouble = URec Double type UFloat = URec Float type UInt = URec Int type UWord = URec Word
Например, следующее объявление данных:
data IntHash = IntHash Int# deriving Generic
приводит к созданию следующего экземпляра Generic:
instance 'Generic' IntHash where
type 'Rep' IntHash =
'D1' ('MetaData "IntHash" "Main" "package-name" 'False)
('C1' ('MetaCons "IntHash" 'PrefixI 'False)
('S1' ('MetaSel 'Nothing
'NoSourceUnpackedness
'NoSourceStrictness
'DecidedLazy)
'UInt'))
Например, пользователь может определить экземпляр GSerialize UInt, чтобы экземпляр Serialize IntHash можно было легко определить через GSerialize.
6.19.3.4. Обобщённые реализации по умолчанию
Осталось определить класс «внешнего интерфейса», доступный пользователю:
class Serialize a where put :: a -> [Bin] default put :: (Generic a, GSerialize (Rep a)) => a -> [Bin] put = gput . from
Здесь мы используем сигнатуру по умолчанию, чтобы указать, что пользователю не нужно предоставлять реализацию для put, если для инстанцируемого типа существует экземпляр Generic. Например, для типа UserTree пользователь может просто написать:
instance (Serialize a) => Serialize (UserTree a)
В этом случае используется метод по умолчанию для put, соответствующий обобщённой реализации сериализации. При использовании DeriveAnyClass тот же экземпляр генерируется простым добавлением предложения deriving Serialize к объявлению типа данных UserTree. Другие примеры обобщённых функций см. в пакете generic-deriving на Hackage.
6.19.3.5. Дополнительная информация
Дополнительные сведения см. на странице Haskell Wiki или в оригинальной статье [Generics2010].
Jose Pedro Magalhaes, Atze Dijkstra, Johan Jeuring и Andres Loeh. Механизм обобщённого вывода для Haskell. Материалы третьего симпозиума ACM по Haskell (Haskell’2010), с. 37–48, ACM, 2010.
