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 выглядел бы точно так же, за исключением того, что каждое вхождение Right заменялось бы на Wrong. Проблема теперь в том, что 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 ||]
-}