6.6.4. Вывод экземпляров дополнительных классов (Data и т. д.)

6.6.4.1. Выведение экземпляров Functor

DeriveFunctor

Подразумевается:

DeriveTraversable

С:

7.10.1

Статус:

Включено в GHC2024, GHC2021

Разрешает автоматическое выведение экземпляров для типа Functor.

С помощью DeriveFunctor можно вывести экземпляры Functor для типов данных типа Type -> Type. Например, это объявление:

data Example a = Ex a Char (Example a) (Example Char)
  deriving Functor

сгенерирует следующий экземпляр:

instance Functor Example where
  fmap f (Ex a1 a2 a3 a4) = Ex (f a1) a2 (fmap f a3) a4

Базовый алгоритм для DeriveFunctor проходит по аргументам каждого конструктора типа данных, применяя функцию отображения в зависимости от типа каждого аргумента. Если найдена простая переменная типа, которая синтаксически эквивалентна последнему параметру типа типа данных (a в приведенном выше примере), то мы применяем функцию f непосредственно к ней. Если обнаружен тип, не синтаксически эквивалентный последнему параметру типа, но упоминающий его где-то, то выполняется рекурсивный вызов fmap. Если обнаружен тип, который вообще не упоминает последний параметр типа, то он оставляется без изменений.

Второй из этих случаев, в котором тип не равен параметру типа, но содержит параметр типа, может быть удивительно сложным. Например, следующий пример компилируется:

newtype Right a = Right (Either Int a) deriving Functor

Однако, немного изменив код, мы получим код, который не будет компилироваться:

newtype Wrong a = Wrong (Either a Int) deriving Functor

Разница заключается в расположении последнего параметра типа, a. В случае Right, a встречается в типе Either Int a, и, кроме того, он появляется в качестве последнего аргумента типа Either. Однако в случае Wrong, a не является последним аргументом типа Either; скорее, им является Int.

Это различие важно из-за того, как работает DeriveFunctor. Полученный экземпляр Functor Right будет:

instance Functor Right where
  fmap f (Right a) = Right (fmap f a)

Учитывая значение типа Right a, GHC должен произвести значение типа Right b. Поскольку аргумент конструктора Right имеет тип Either Int a, код рекурсивно вызывает fmap для него, чтобы произвести значение типа Either Int b, которое в свою очередь используется для построения конечного значения типа Right b.

Сгенерированный код для экземпляра Functor Wrong будет выглядеть точно так же, за исключением того, что Wrong заменит каждое вхождение Right. Проблема теперь в том, что fmap рекурсивно применяется к значению типа Either a Int. Это не может произвести значение типа Either b Int, поскольку fmap может изменить только последний параметр типа! Это приводит к тому, что сгенерированный код не типизирован.

В качестве общего правила, если тип данных имеет экземпляр Functor и его последний параметр типа появляется справа в объявлении типа данных, то он либо (1) должен появляться без обертки (например, newtype Id a = Id a), либо (2) должен появляться в качестве последнего аргумента конструктора типа (как в Right выше).

Есть два исключения из этого правила:

1. Типы кортежей. Когда в правой части объявления типа данных используется кортеж, отличный от единичного, DeriveFunctor рассматривает его как произведение различных типов. Другими словами, следующий код:

   newtype Triple a = Triple (a, Int, [a]) deriving Functor
   

   Приведет к сгенерированному экземпляру Functor такого вида:

   instance Functor Triple where
     fmap f (Triple a) =
       Triple (case a of
                    (a1, a2, a3) -> (f a1, a2, fmap f a3))
   

   То есть, DeriveFunctor продвигается внутрь кортежей и применяет отображение к каждому типу, составляющему кортеж. Сгенерированный код напоминает то, что было бы сгенерировано из data Triple a = Triple a Int [a], за исключением дополнительных механизмов для работы с кортежем.

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

   newtype CovFun1 a = CovFun1 (Int -> a) deriving Functor
   newtype CovFun2 a = CovFun2 ((a -> Int) -> a) deriving Functor
   newtype CovFun3 a = CovFun3 (((Int -> a) -> Int) -> a) deriving Functor
   

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

   newtype ContraFun1 a = ContraFun1 (a -> Int) deriving Functor
   newtype ContraFun2 a = ContraFun2 ((Int -> a) -> Int) deriving Functor
   newtype ContraFun3 a = ContraFun3 (((a -> Int) -> a) -> Int) deriving Functor
   

   Хотя эти примеры выглядят похожими, ни один из них не будет успешно компилироваться. Это происходит потому, что все вхождения последнего параметра типа a находятся в контравариантных позициях, а не ковариантных.

   Интуитивно, ковариантный тип производится, а контравариантный тип потребляется. Большинство типов в Haskell ковариантны, но тип функции является особенным тем, что левая сторона стрелки функции меняет вариацию. Если тип функции a -> b появляется в ковариантной позиции (например, CovFun1 выше), то a находится в контравариантной позиции, а b находится в ковариантной позиции. Аналогично, если a -> b появляется в контравариантной позиции (например, CovFun2 выше), то a находится в a ковариантной позиции, а b — в контравариантной.

   Чтобы понять, почему тип данных с контравариантным вхождением его последнего параметра не может иметь экземпляра Functor, предположим, что экземпляр Functor ContraFun1 существует. Реализация будет выглядеть примерно так:

   instance Functor ContraFun1 where
     fmap f (ContraFun g) = ContraFun (\x -> _)
   

   У нас есть f :: a -> b, g :: a -> Int и x :: b. Используя их, мы должны как-то заполнить пробел (обозначенный подчеркиванием) значением типа Int. Какие у нас есть варианты?

   Мы могли бы попробовать применить g к x. Однако это не сработает, так как g ожидает аргумент типа a, а x :: b. Еще хуже, мы не можем превратить x во что-то типа a, так как f также требует аргумента типа a! Короче говоря, нет хорошего способа сделать это.

   С другой стороны, экземпляры Functor для CovFun находятся в рамках возможностей:

   instance Functor CovFun1 where
     fmap f (CovFun1 g) = CovFun1 (\x -> f (g x))
   
   instance Functor CovFun2 where
     fmap f (CovFun2 g) = CovFun2 (\h -> f (g (\x -> h (f x))))
   
   instance Functor CovFun3 where
     fmap f (CovFun3 g) = CovFun3 (\h -> f (g (\k -> h (\x -> f (k x)))))
   

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

1. Тип данных не имеет параметров типа (например, data Nothing = Nothing).
2. Последняя переменная типа типа данных используется в ограничении DatatypeContexts (например, data Ord a => O a = O a).

3. Последняя переменная типа типа данных используется в ограничении ExistentialQuantification или уточняется в GADT. Например,

   data T a b where
       T4 :: Ord b => b -> T a b
       T5 :: b -> T b b
       T6 :: T a (b,b)
   
   deriving instance Functor (T a)
   

   не будет успешно компилироваться из-за того, как ограничено b.

Когда последний параметр типа имеет роль фиктивного параметра (см. Роли), сгенерированный экземпляр Functor не будет создан с помощью обычного алгоритма. Вместо этого все значение будет приведено.

data Phantom a = Z | S (Phantom a) deriving Functor

выведет следующий экземпляр:

instance Functor Phantom where
  fmap _ = coerce

Когда у типа нет конструкторов, экземпляр Functor просто принудительно устанавливает (нижнее) значение аргумента с помощью EmptyCase.

data V a deriving Functor
type role V nominal

выведет

instance Functor V where
  fmap _ z = case z of

6.6.4.2. Вывод экземпляров Foldable

DeriveFoldable

Подразумевается:

DeriveTraversable

С:

7.10.1

Статус:

Включено в GHC2024, GHC2021

Разрешить автоматический вывод экземпляров для класса типов Foldable.

С помощью DeriveFoldable можно вывести экземпляры Foldable для типов данных вида Type -> Type. Например, эта декларация:

data Example a = Ex a Char (Example a) (Example Char)
  deriving Foldable

сгенерирует следующий экземпляр:

instance Foldable Example where
  foldr f z (Ex a1 a2 a3 a4) = f a1 (foldr f z a3)
  foldMap f (Ex a1 a2 a3 a4) = mappend (f a1) (foldMap f a3)

Алгоритм для DeriveFoldable адаптирован из алгоритма DeriveFunctor, но он генерирует определения для foldMap, foldr и null вместо fmap. Кроме того, DeriveFoldable отфильтровывает все аргументы конструкторов в правой части выражения, типы которых не упоминают последний параметр типа, так как эти аргументы не нужно сворачивать.

Когда параметр типа играет роль фантома (см. Роли), DeriveFoldable выводит тривиальный экземпляр. Например, эта декларация:

data Phantom a = Z | S (Phantom a)

сгенерирует следующий экземпляр.

instance Foldable Phantom where
  foldMap _ _ = mempty

Аналогично, если тип не имеет конструкторов, DeriveFoldable выведет тривиальный экземпляр:

data V a deriving Foldable
type role V nominal

сгенерирует следующее.

instance Foldable V where
  foldMap _ _ = mempty

Вот различия между сгенерированным кодом для Functor и Foldable:

#. Когда встречается голое имя переменной типа a, DeriveFunctor сгенерирует f a для определения fmap. DeriveFoldable сгенерирует f a z для foldr, f a для foldMap и False для null.

1. Когда встречается тип, который не является синтаксически эквивалентным типу a, но содержит a, DeriveFunctor рекурсивно вызывает fmap для него. Аналогично, DeriveFoldable будет рекурсивно вызывать foldr и foldMap. В зависимости от контекста, null может рекурсивно вызывать null или all null. Например, для

   data F a = F (P a)
   data G a = G (P (a, Int))
   data H a = H (P (Q a))
   

   Foldable вывод будет

   null (F x) = null x
   null (G x) = null x
   null (H x) = all null x
   

2. DeriveFunctor собирает все обратно в конце, вызывая конструктор. DeriveFoldable, однако, строит значение некоторого типа. Для foldr это достигается цепочкой применений f и рекурсивных вызовов foldr на значении состояния z. Для foldMap это происходит путем объединения всех значений с помощью mappend. Для null значения обычно объединяются с помощью &&. Однако, если какое-либо из значений известно как False, все остальные будут отброшены. Например,

   data SnocList a = Nil | Snoc (SnocList a) a
   

   не даст

   null (Snoc xs _) = null xs && False
   

   а скорее

   null (Snoc _ _) = False
   

Существуют и другие различия, касающиеся типов данных, которые могут иметь выведенные экземпляры Foldable:

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

2. Экземпляры Foldable могут быть выведены для типов данных, в которых последний параметр типа существует или уточняется в GADT. Например, этот тип данных:

   data E a where
       E1 :: (a ~ Int) => a   -> E a
       E2 ::              Int -> E Int
       E3 :: (a ~ Int) => a   -> E Int
       E4 :: (a ~ Int) => Int -> E a
   
   deriving instance Foldable E
   

   будет иметь следующий сгенерированный экземпляр Foldable:

   instance Foldable E where
       foldr f z (E1 e) = f e z
       foldr f z (E2 e) = z
       foldr f z (E3 e) = z
       foldr f z (E4 e) = z
   
       foldMap f (E1 e) = f e
       foldMap f (E2 e) = mempty
       foldMap f (E3 e) = mempty
       foldMap f (E4 e) = mempty
   

   Обратите внимание, как каждый конструктор E использует какой-то вид экзистенциального квантификатора, но только аргумент E1 фактически «сворачивается». Это потому, что мы сознательно выбираем сворачивать только универсально полиморфные типы, которые синтаксически эквивалентны последнему параметру типа. В частности:

• Мы не сворачиваем аргументы E1 или E4, потому что хотя (a ~ Int), Int не синтаксически эквивалентно типу a.
• Мы не сворачиваем аргумент E3, потому что a не универсально полиморфен. a в E3 (неявно) экзистенциально квантифицировано, поэтому оно не то же самое, что последний параметр типа E.

6.6.4.3. Вывод экземпляров Traversable

DeriveTraversable

Подразумевает:

DeriveFoldable, DeriveFunctor

Подразумевается:

GHC2021

С:

7.10.1

Разрешить автоматический вывод экземпляров для класса типов Traversable.

С помощью DeriveTraversable можно вывести экземпляры Traversable для типов данных вида Type -> Type. Например, эта декларация:

data Example a = Ex a Char (Example a) (Example Char)
  deriving (Functor, Foldable, Traversable)

сгенерирует следующий экземпляр Traversable:

instance Traversable Example where
  traverse f (Ex a1 a2 a3 a4)
    = fmap (\b1 b3 -> Ex b1 a2 b3 a4) (f a1) <*> traverse f a3

Алгоритм для DeriveTraversable адаптирован из алгоритма DeriveFunctor, но он генерирует определение для traverse вместо fmap. Кроме того, DeriveTraversable отфильтровывает все аргументы конструкторов в правой части выражения, типы которых не упоминают последний параметр типа, так как эти аргументы не оказывают никакого влияния в процессе обхода.

Когда параметр типа имеет фантомную роль (см. Роли), DeriveTraversable выполняет приведение своего аргумента. Например, эта декларация:

data Phantom a = Z | S (Phantom a) deriving Traversable

сгенерирует следующий экземпляр:

instance Traversable Phantom where
  traverse _ z = pure (coerce z)

Если тип не имеет конструкторов, DeriveTraversable выведет самый ленивый экземпляр, который может.

data V a deriving Traversable
type role V nominal

сгенерирует следующее, используя EmptyCase:

instance Traversable V where
  traverse _ z = pure (case z of)

Вот различия в сгенерированном коде в каждом расширении:

1. Когда встречается голое имя переменной типа a, как DeriveFunctor, так и DeriveTraversable сгенерируют f a для определения fmap и traverse, соответственно.
2. Когда встречается тип, не синтаксически эквивалентный типу a, но содержащий a, DeriveFunctor рекурсивно вызывает fmap на нем. Аналогично, DeriveTraversable рекурсивно вызовет traverse.
3. DeriveFunctor собирает все обратно в конце, вызывая конструктор. DeriveTraversable делает нечто подобное, но работает в контексте Applicative, соединяя все вместе с помощью (<*>).

В отличие от DeriveFunctor, DeriveTraversable нельзя использовать для типов данных, содержащих тип функции в правой части.

Для полного описания алгоритмов, используемых в DeriveFunctor, DeriveFoldable и DeriveTraversable, см. эту страницу вики.

6.6.4.4. Получение экземпляров Data

DeriveDataTypeable

С момента:

6.8.1

Статус:

Включено в GHC2024, GHC2021

Включить автоматическое получение экземпляров для типокласса Data

6.6.4.5. Получение экземпляров Typeable

Класс Typeable очень особый:

• Typeable имеет полиморфизм по типу (см. Полиморфизм по типу).
• GHC имеет пользовательский решатель для разрядки ограничений, включающих класс Typeable, и ручные экземпляры запрещены. Это гарантирует, что программист не может обойти систему типов, написав поддельные экземпляры.
• Производные экземпляры Typeable могут быть объявлены, если включен расширение DeriveDataTypeable, но они игнорируются, и они могут быть сообщены как ошибка в более поздней версии компилятора.

• Правила решения ограничений Typeable следующие:

  • Конструктор конкретного типа, примененный к некоторым типам.

    instance (Typeable t1, .., Typeable t_n) =>
      Typeable (T t1 .. t_n)
    

    Это правило работает для любого конкретного конструктора типа, включая конструкторы типов с полиморфными типами. Единственное ограничение состоит в том, что если конструктор типа имеет полиморфный тип, то он должен быть применен ко всем своим параметрам типов, и эти типы должны быть конкретными (т. е. они не могут упоминать переменные типов).

  • Переменная типа, применённая к некоторым типам:

    instance (Typeable f, Typeable t1, .., Typeable t_n) =>
      Typeable (f t1 .. t_n)
    

  • Конкретная буква типа.:

    instance Typeable 0       -- Type natural literals
    instance Typeable "Hello" -- Type-level symbols
    

6.6.4.6. Получение экземпляров Lift

DeriveLift

С момента:

8.0.1

Статус:

Включено в GHC2024, GHC2021

Включить автоматическое получение экземпляров для типокласса Lift для Template Haskell.

Класс Lift, в отличие от других производных классов, находится в template-haskell, а не в base. Наличие типа данных в качестве экземпляра Lift позволяет продвигать его значения до выражений Template Haskell (типа ExpQ и Code Q a), которые затем могут быть вставлены в исходный код Haskell.

Вот пример того, как можно получить Lift:

{-# LANGUAGE DeriveLift #-}
module Bar where

import Language.Haskell.TH.Syntax

data Foo a = Foo a | a :^: a deriving Lift

{-
instance (Lift a) => Lift (Foo a) where
    lift (Foo a) = [| Foo a |]
    lift ((:^:) u v) = [| (:^:) u v |]

    liftTyped (Foo a) = [|| Foo a ||]
    liftTyped ((:^:) u v) = [|| (:^:) u v ||]
-}

-----
{-# LANGUAGE TemplateHaskell #-}
module Baz where

import Bar
import Language.Haskell.TH.Lift

foo :: Foo String
foo = $(lift $ Foo "foo")

fooExp :: Lift a => Foo a -> Q Exp
fooExp f = [| f |]

Обратите внимание, что типокласс Lift использует Полиморфизм представления, чтобы поддерживать экземпляры, включающие не упакованные типы. Это означает, что DeriveLift также работает для этих типов:

{-# LANGUAGE DeriveLift, MagicHash #-}
module Unboxed where

import GHC.Exts
import Language.Haskell.TH.Syntax

data IntHash = IntHash Int# deriving Lift

{-
instance Lift IntHash where
    lift (IntHash i) = [| IntHash i |]
    liftTyped (IntHash i) = [|| IntHash i ||]
-}