追加の型クラスのインスタンス導出 (Data, etc.)
Haskell 98 では,deriving節に指定されたクラスの標準的なインスタンス宣言を生成するために,データ型の宣言に「deriving (Eq, Ord)」などというものを付加することをプログラマに許している.Haskell 98においては,deriving節に登場することが許されるクラスは標準クラスEq・Ord・Enum・Ix・Bounded・Read・Showのみである.
GHCは,以上のリストに加えて,自動的に導出できるクラスをさらに数個提供する.
DeriveGeneric を使うと,GHC.Generics で定義されている GenericクラスとGeneric1 クラスのインスタンスを導出することができる.これを使うことで,Generic programming に書かれている通り,総称関数を定義することができる. DeriveFunctorを使うと,GHC.Baseで定義されているFunctorクラスのインスタンスを導出することができる.
DeriveDataTypeableを使うと,Data.Dataで定義されているDataクラスのインスタンスを導出することができる.
DeriveFoldableを使うと,Data.Foldableで定義されているFoldableクラスのインスタンスを導出することができる.
DeriveTraversableを使うと,Data.Traversableで定義されているTraversableクラスのインスタンスを導出することができる.TraversableインスタンスというのはFunctorのインスタンス・Foldableのインスタンスを規定するものである以上,FunctorやFoldableも導出したくなるわけで,ゆえにDeriveTraversableはDeriveFunctor と DeriveFoldable を含む.
DeriveLiftを使うと,template-haskell パッケージの Language.Haskell.TH.Syntaxモジュールで定義されているLiftクラスのインスタンスを導出することができる.
以上のどの場合においても,deriving節でクラスに言及するためにはそのクラスがあらかじめスコープに導入されている必要がある.
Functorのインスタンス導出
DeriveFunctor
7.10.1以降
Functor型クラスのインスタンスを自動で導出することを可能にする.
DeriveFunctorがあれば,種がType -> Typeであるデータ型に対してFunctorを導出することができる.例えば,以下の宣言は
code:de99.hs
data Example a = Ex a Char (Example a) (Example Char)
deriving Functor
以下のインスタンスを生成するだろう.
code:de98.hs
instance Functor Example where
fmap f (Ex a1 a2 a3 a4) = Ex (f a1) a2 (fmap f a3) a4
DeriveFunctorの基本的なアルゴリズムは,データ型の各コンストラクタの引数を走査し,それぞれの引数の型に応じて射関数を適用するというものである.データ型の最後の型引数と構文上等価である生の型引数が見つかった場合(上記例のa),関数fをそれに直接適用する.データ型の最後の型引数と構文上等価ではないが,内部で最後の型引数に言及はしている型に遭遇した場合,fmapへの再帰的呼び出しが行われる.最後の型引数に一切言及していない型が見つかった場合,その型はそのままにされる.(訳注:de98.hsでは,生の型引数はa(a1),構文上等価ではないが,内部で最後の型引数に言及はしている型は,Example a(a3)のことを指す.)
型が型パラメータに等しくないが型パラメータを含んでいる場合という,上記の二番目のケースは,驚くほどトリッキーになりうる.例えば,次のコードはコンパイルが通る.
code:de97.hs
newtype Right a = Right (Either Int a) deriving Functor
しかしながら,コードを少し改変すると,コンパイルの通らない以下のようなコードが生成される.
code:de96.hs
newtype Wrong a = Wrong (Either a Int) deriving Functor
この違いは,最後の型パラメータaの置かれる位置と関係がある.Rightでは,aは型 Either Int aの中に登場し,さらに,aはEitherの最後の型引数として登場する.一方,Wrongでは,aはEitherの最後の型引数ではなく,Eitherの最後の型引数はIntである(訳注:これはη変換っぽいのができるか否かという違いである).
DeriveFunctorの仕組みの都合上,この違いは重要である.導出されたRightFunctorのインスタンスは以下のようになる.
code:de95.hs
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の型を持つ最終的な値を構成するために用いられる.
WrongFunctorのインスタンス用の自動生成されたコードは,Rightが全てWrongに置き換わっていることを除けば全く同じ見た目となることであろう.問題は,今度はfmapがEither a Int型の値に再帰的に適用されていることである.fmapは最後の型パラメータしか変えることができない以上,これによりEither b Intの型を持つ値を生み出せるわけがない.これにより,生成されたコードはill-typedとなる.
一般的な規則として,データ型に対してFunctorのインスタンスが導出でき,その最後の型パラメータがデータ宣言の右辺にある場合,以下のいずれかである必要がある.(1) 裸で登場する場合.(例えば,newtype Id a = Id a) (2) 型コンストラクタの最後の引数として登場する場合.(上記のRightのように)
この規則には例外が2つある:
1. タプル型.()でないタプルがデータ宣言の右辺で用いられている場合,DeriveFunctorはそれを相異なる型の積として扱う.言い換えれば,次のコード
code:de94.hs
newtype Triple a = Triple (a, Int, a) deriving Functor は,以下のようなFunctorインスタンスを生成する.
code:de93.hs
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. 関数型.最後の型パラメータは,共変な位置に登場する限り関数型内の任意の位置に登場できる.これがどういう意味かを例証すべく,次の三つの例を考えよう:
code:de92.hs
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
これら三例はどれも問題なくコンパイルできる. 一方で,
code:de91.hs
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
これら三例は(de92.hsの三例と)見た目が似ているものの,どれもコンパイルに失敗する.なぜなら,最後の型パラメータaが全て(共変的位置ではなく)反変的位置に現れているからである.
直感的には,共変な型というのは生成されるもののことであり,反変な型というのは消費されるもののことである.Haskellにおけるほとんどの型は共変であるが,「関数の矢印の左側は反変と共変が逆転する」という点で関数型は特別である.関数型a -> bが共変的位置に現れるならば(例:上のCovFun1),aは反変的位置に在り,bは共変的位置に在る.同様に,a -> bが反変的位置に現れるならば(例:上のCovFun2),aは共変的位置に在り,bは反変的位置に在る.
最後の型パラメータが反変的位置に登場するデータ型が導出されたFunctorインスタンスをなぜ持つことができないかを理解するために,Functor ContraFun1インスタンスが存在すると仮定してみよう.すると実装は以下のコードっぽいなにかになるはずである.
code:de90.hs
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だからである.さらに悪いことに,型aを持つ値へとxを変えることも不可能である.なぜなら,fもまた型aを持つ値を要求しているからである.要するに,これを上手くいくようにする良い方法はない.
一方で,CovFunsのFunctorのインスタンス導出はできる:
code:de89.hs
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内で篩にかけられているとき.例えば,
code:de88.hs
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 の制約のされ方が原因でコンパイルに失敗する.
最後の型パラメータがphantom role (Rolesを参照せよ) を持つときは,導出された Functor インスタンスは通常のアルゴリズムによって生成されるわけではない.代わりに,値全体がcoerceされる.
code:de87.hs
data Phantom a = Z | S (Phantom a) deriving Functor
は,以下のインスタンスを生成する.
code:de86.hs
instance Functor Phantom where
fmap _ = coerce
型にコンストラクタがない場合,導出されたFunctorインスタンスは単純にEmptyCaseを用いて引数の(bottom)値を強制的に評価する.
code:de85.hs
data V a deriving Functor
type role V nominal
は,以下のコードを生成する.
code:de84.hs
instance Functor V where
fmap _ z = case z of
Foldableのインスタンス導出
DeriveFoldable
7.10.1以降
Foldable型クラスのインスタンスを自動で導出することを可能にする.
DeriveFoldableがあれば,種がType -> Typeであるデータ型に対してFoldableを導出することができる.例えば,以下の宣言は
code:de83.hs
data Example a = Ex a Char (Example a) (Example Char)
deriving Foldable
以下のインスタンスを生成する:
code:de82.hs
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のアルゴリズムを元に構成されているが,fmapの代わりにfoldMap, foldr, nullの定義を生成する.加えて,右辺の式の全てのコンストラクタ引数のうち,最後の型パラメータに言及していない型を持つものに関しては,それらを畳み込む必要がないため,DeriveFoldableはそれらを除外する.
型引数がphantom role (see Roles)を持つとき, DeriveFoldable は自明なインスタンスを導出する.例えば,以下の宣言は
code:de81.hs
data Phantom a = Z | S (Phantom a)
以下のインスタンスを生成する:
code:de80.hs
instance Foldable Phantom where
foldMap _ _ = mempty
同様に,型が値コンストラクタを持たない場合,DeriveFoldableは自明なインスタンスを導出する.
code:de79.hs
data V a deriving Foldable
type role V nominal
は,以下のコードを生成する.
code:de78.hs
instance Foldable V where
foldMap _ _ = mempty
ここで,FunctorとFoldableの生成するコードの違いは:
#. 裸の型変数aを見つけると,DeriveFunctorはfmapの定義としてf aを生成する.DeriveFoldableはfoldrの場合はf a zを,foldMapの場合はf aを.nullの場合はFalseを生成する. 1. aと構文上等価ではないもののaを含んでいる型に遭遇した場合,DeriveFunctorはそれに対して再帰的にfmapを呼ぶ. 同様に,DeriveFoldableは再帰的にfoldrとfoldMapを呼ぶ.文脈に応じて,nullはnullかall nullを再帰的に呼び出すことがある.例えば:
code:de77.hs
data F a = F (P a)
data G a = G (P (a, Int))
data H a = H (P (Q a))
Foldableは以下を導出する:
code:de76.hs
null (F x) = null x
null (G x) = null x
null (H x) = all null x
2. DeriveFunctorは,最後にコンストラクタを呼び出すことで全部を(訳注:f bの型を持つ一つの値へと)組み立て直す.しかし,DeriveFoldableは何らかの値を作り上げる(訳注:そして,作り上げられるその値には必ずしも値コンストラクタが関与しない).foldrの場合,これはfを関数適用することと再帰的にfoldrが状態値zを呼び出すこととをつなげることでなされる.foldMapの場合,これはすべての値をmappendで合体させることによってなされる.nullの場合,値は通常,&&で合体される.しかしながら,どれか一つでもFalseであることが確定している場合,残りの値は全て捨てられる.例えば,
code:de75.hs
data SnocList a = Nil | Snoc (SnocList a) a
は,(リスト全体を走査してしまうコードである)↓ではなく,
code:de74.hs
null (Snoc xs _) = null xs && False
↓を生成する.
code:de73.hs
null (Snoc _ _) = False
どのデータ型がFoldableのインスタンスを導出できるかに関して,他にもいくつかの違いがある:
1. 右辺に関数型を含むデータ型は,Foldableのインスタンスを導出することはできない.
2. Foldableのインスタンスは,最後の型パラメータが存在的に制約されていたり,GADTの篩わけに使われていたりしても導出することができる.例えば次のデータ型を考えてみよう:
code:de72.hs
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のインスタンスを生成するだろう:
code:de71.hs
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の引数の上でのみ畳み込まれている.これは,最後の型パラメータと構文的に等価な普遍的多相型のみを畳み込むという意図的な(訳注:設計上の)選択をしているからである.特に:
(a ~ Int),Intが構文的にaと等価でないにもかかわらず,E1やE4の引数を畳み込むことはしない.
aは普遍的多相ではないので,我々はE3の引数を畳み込まない.E3のaは(暗黙のうちに)存在量化されているので,Eの最後の型パラメータと同じではない.
Traversableのインスタンス導出
DeriveTraversable
DeriveFoldable, DeriveFunctor を含む
7.10.1以降
Traversable 型クラスのインスタンスを自動で導出することを可能にする.
DeriveTraversableがあれば,種がType -> Typeであるデータ型に対してTraversableを導出することができる.例えば,以下の宣言は,
code:de70.hs
data Example a = Ex a Char (Example a) (Example Char)
deriving (Functor, Foldable, Traversable)
以下のようなTraversableインスタンスを生成する.
code:de69.hs
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のアルゴリズムを元に構成されているが,fmapの代わりにtraverseの定義を生成する.加えて,右辺の式の全てのコンストラクタ引数のうち,最後の型パラメータに言及していない型を持つものに関しては,traverseに影響を与えないので,DeriveFoldableはそれらを除外する.
型引数がphantom role (Rolesを参照せよ)を持つとき,DeriveTraversable は引数をcoerceする. 例えば,以下の宣言は,
code:de68.hs
data Phantom a = Z | S (Phantom a) deriving Traversable
以下のようなインスタンスを生成する.
code:de67.hs
instance Traversable Phantom where
traverse _ z = pure (coerce z)
型にコンストラクタがない場合,DeriveTraversableは可能な限りlazyなインスタンスを導出する.
code:de66.hs
data V a deriving Traversable
type role V nominal
EmptyCaseを用いて以下のように生成される:
code:de65.hs
instance Traversable V where
traverse _ z = pure (case z of)
ここで,各拡張の生成するコードの違いは:
1. 裸の型変数aを見つけると,DeriveFunctorとDervieTraversableは共にfmap, traverseそれぞれの定義でf aを生成する.
2. aと構文上等価でないもののaを含む型に遭遇した場合,DeriveFunctorはそれに対して再帰的にfmapを呼ぶ.同様に,DeriveTraversableは再帰的にtraverseを呼ぶ.
3. DeriveFunctorは,最後にコンストラクタを呼び出すことで全部を(訳注:f bの型を持つ一つの値へと)組み立て直す.DeriveTraversableは同様であるが,Applicative制約のもとで,(<*>)ですべてつなげる.
DeriveFunctorとは異なり,DeriveTraversableは右辺に関数型を含んでいるデータ型に対しては使うことができない.
DeriveFunctor・ DeriveFoldable・ DeriveTraversableで用いられているアルゴリズムの正式な仕様については,このwikiページを参照せよ. Dataのインスタンス導出
DeriveDataTypeable
6.8.1以降
Data 型クラスのインスタンスを自動で導出することを可能にする.
Typeableのインスタンス導出
Typeable型クラスはとても特別な型クラスである:
Typeableは種多相である(種多相を参照せよ). GHCは Typeableクラスに関連する制約を解消するためのカスタムソルバを持っており,Typeableクラスのインスタンスを手で書くのは禁止されている.これによって,プログラマがインチキなインスタンスを書いて型システムを壊すことが不可能であることが保証される.
DeriveDataTypeable拡張が有効化されていればTypeableの導出されたインスタンスを宣言することができるが,その宣言は無視されるし,コンパイラの将来のバージョンではエラーとして報告されるようになるかもしれない.
Typeable制約を解決するためのルールは以下の通りである:
なんらかの型に関数適用されている具体的な型コンストラクタ:
code:de64.hs
instance (Typeable t1, .., Typeable t_n) =>
Typeable (T t1 .. t_n)
この規則は,多相的な種を持つ型コンストラクタを含む任意の具体的な型コンストラクタに対して適用される.唯一の制限は,型コンストラクタが多相的な種を持つ場合,全ての種パラメータにそれらの型(訳注:上記で述べているなんらかの型のこと)が適用されていなければならず,そしてこれらの種は具体的でなければならない(つまり,種変数に言及していてはいけない).
なんらかの型に関数適用されている型変数:
code:de63.hs
instance (Typeable f, Typeable t1, .., Typeable t_n) =>
Typeable (f t1 .. t_n)
具体的な型リテラル:
code:de62.hs
instance Typeable 0 -- Type natural literals
instance Typeable "Hello" -- Type-level symbols
Deriving Lift instances
DeriveLift
7.2.1以降
Template HaskellのLift型クラスのインスタンスを自動で導出することを可能にする.
Liftクラスは,他の導出可能な型クラスと異なり,baseではなく template-haskell内にある.データ型がLiftのインスタンスであるというのは,そのデータ型を持つ値がTemplate Haskellの式(その式は型 ExpQを持つ)に昇格され,そしてその後Haskellソースコードの中へとspliceされることが可能であることを表す.
以下は,どのようにしてLiftを導出することができるかの例である.
code:de61.hs
{-# 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)
= appE
(conE
(mkNameG_d "package-name" "Bar" "Foo"))
(lift a)
lift (u :^: v)
= infixApp
(lift u)
(conE
(mkNameG_d "package-name" "Bar" ":^:"))
(lift 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 |
DeriveLift は いくつかのUnboxedな型(Addr#・Char#・Double#・Float#・Int#・Word#)に対しても機能する.
code:de60.hs
{-# 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)
= appE
(conE
(mkNameG_d "package-name" "Unboxed" "IntHash"))
(litE
(intPrimL (toInteger (I# i))))
-}