GHC Generic Programming と代数的データ型

Haskell Advent Calendar 2016 の 12日目のエントリーです。

代数的データ型と Functor

Generic Programming は代数的データ型の構造を Functor の直積と直和のネスト構造に対応付けることで、 任意の代数的データ型に対する操作の記述を可能にする仕組みです。

まずは理解のために、より単純化した構造で考えてみましょう。

次のようなデータ型 ProdF f g a を考えると、 ProdF f g は Functor f および Functor g のもとで Functor になります。 これは、 もとの Functor のそれぞれの像の直積も Functor になる ということです。

ほぼ自明な内容ですが、 functor則を満たしていることを下に簡単に示してあります。

data ProdF f g a = ProdF (f a) (g a)

instance (Functor f, Functor g) => Functor (ProdF f g) where
  fmap f (ProdF p q) = ProdF (fmap f p) (fmap f q)

{-    fmap id
      {- ProdF の fmap の定義を unfold -}
   =  \(ProdF p q) -> ProdF (fmap id p) (fmap id q)
      {- Functor f および Functor g において fmap id == id -}
   =  \(ProdF p q) -> ProdF p q
   =  id

      fmap (f . g)
      {- ProdF の fmap の定義を unfold -}
   =  \(ProdF p q) -> ProdF (fmap (f . g) p) (fmap (f . g) q)
      {- fmap (f . g) == fmap f . fmap g -}
   =  \(ProdF p q) -> ProdF ((fmap f . fmap g) p) ((fmap f . fmap g) q)
      {- 関数合成の分離 -}
   =  (\(ProdF p q) -> ProdF (fmap f p) (fmap f q)) . (\(ProdF p q) -> ProdF (fmap g p) (fmap g q))
      {- ProdF の fmap の定義を fold -}
   =  fmap f . fmap g
 -}

Control.Applicative モジュールにある Const functor を使って ProdF (Const a) (Const b) x を考えると、これは値の直積 (a, b) と同型( 互いに変換してもプログラムの持つ意味を保存する )になることがわかります。 以下で、互いへの変換の関数の定義と、 その関数の合成が向きがどちらでも恒等関数になることを示しています。

prodFrom :: (a, b) -> ProdF (Const a) (Const b) x
prodFrom (p, q) = ProdF (Const p) (Const q)

prodTo :: ProdF (Const a) (Const b) x -> (a, b)
prodTo (ProdF (Const p) (Const q)) = (p, q)

{-
      prodFrom . prodTo $ ProdF (Const p) (Const q)
   =  prodFrom  (p, q)
   =  prodF (Const p) (Const q)
 -}

{-
      prodTo . prodFrom $ (p, q)
   =  prodTo  (ProdF (Const p) (Const q))
   =  (p, q)
 -}

このように直積の構造を functor の中に保存することが可能です。

直和の場合も考えてみましょう。

次のようなデータ型 SumF f g x を考えると、 SumF f g は Functor f および Functor g のもとでやはり Functor になります。 これは、 もとの Functor のそれぞれの像の直和も Functor になる ということです。

やはりほぼ自明な内容ですが、 functor則を満たしていることを下に簡単に示してあります。

data SumF f g x
  = SumL (f x)
  | SumR (g x)

instance (Functor f, Functor g) => Functor (SumF f g) where
  fmap f (SumL p) = SumL (fmap f p)
  fmap f (SumR q) = SumR (fmap f q)

{-    fmap id
      {- SumF の fmap の定義を unfold -}
   =  \x -> case x of { SumL p -> SumL (fmap id p) ; SumR q -> SumR (fmap id q) }
      {- Functor f および Functor g において fmap id == id -}
   =  \x -> case x of { SumL p -> SumL p ; SumR q -> SumR q }
   =  id

      fmap (f . g)
      {- SumF の fmap の定義を unfold -}
   =  \x -> case x of { SumL p -> SumL (fmap (f . g) p) ; SumR q -> SumR (fmap (f . g) q) }
      {- fmap (f . g) == fmap f . fmap g -}
   =  \x -> case x of { SumL p -> SumL ((fmap f . fmap g) p) ; SumR q -> SumR ((fmap f . fmap g) q) }
      {- 関数合成の分離 -}
   =  (\x -> case x of { SumL p -> SumL (fmap f p) ; SumR q -> SumR (fmap f q) }) .
      (\x -> case x of { SumL p -> SumL (fmap g p) ; SumR q -> SumR (fmap g q) })
      {- SumF の fmap の定義を fold -}
   =  fmap f . fmap g
 -}

こちらでも SumF (Const a) (Const b) x を考えると、これは値の直和 Either a b と同型になることがわかります。 直積の場合と同様に、互いへの変換の関数の定義と、 その関数の合成が向きがどちらでも恒等関数になることを示しています。

sumFrom :: Either a b -> SumF (Const a) (Const b) x
sumFrom (Left  p)  =  SumL (Const p)
sumFrom (Right q)  =  SumR (Const q)

sumTo :: SumF (Const a) (Const b) x -> Either a b
sumTo (SumL (Const p))  =  Left  p
sumTo (SumR (Const q))  =  Right q

{-
       sumFrom . sumTo $ SumL (Const p)
    =  sumFrom  (Left p)
    =  sumL p

       sumFrom . sumTo $ SumR (Const q)
    =  sumFrom  (Right q)
    =  sumL q
 -}

{-     sumTo . sumFrom $ Left p
    =  sumTo  (SumL (Const p))
    =  Left p

       sumTo . sumFrom $ Right q
    =  sumTo  (SumR (Const q))
    =  Right q
 -}

このように直和の構造も functor の中に保存することが可能です。

直積と直和の構造を情報を保存したままともに Functor にすることができたので、 これをさらに入れ子にすることで、与えられた任意の代数的データ型と同型になる Functor に変換できることがわかります。

GHC Generic Programming における定義

ここからは GHC.Generics モジュールに定義されている実際の Generic Programming 用の定義を使って見ていきましょう。

上の例での ProdF に対応するのが :*:、 SumF に対応するのが :+:、 Const に対応するのが K1 です。

これに加えて、コンストラクタの情報を保存するための型 M1 (フィールド 1つ以上) U1 (フィールド無し) が用意されています。

data (:*:) f g p = (f p) :*: (g p)
data (:+:) f g p = L1 (f p) | R1 (g p)
newtype K1 i c p = K1 {unK1 :: c}

data U1 p = U1
newtype M1 i c f p = M1 {unM1 :: f p}

代数的データ型と Functor の構造を互いに変換するための関数も見てみましょう。

% ghci
Prelude> import GHC.Generics
Prelude GHC.Generics> :t from
from :: Generic a => a -> Rep a x
Prelude GHC.Generics> :t to
to :: Generic a => Rep a x -> a

a が代数的データ型であるとすると Rep a はそれに対応した構造を持つ Functor です。 from は代数的データ型を Functor のネスト構造に変換し、 to はFunctor のネスト構造を代数的データ型に変換します。 Generic クラスのインスタンスは、 GHC の DeriveGeneric 拡張を使うことで生成することができます。

では直積の構造がどのような Functor に変換されているか見てみましょう。

Prelude GHC.Generics> :t from ( ('a', 1) :: (Char, Int) )
from ( ('a', 1) :: (Char, Int) )
  :: D1
       ('MetaData "(,)" "GHC.Tuple" "ghc-prim" 'False)
       (C1
          ('MetaCons "(,)" 'PrefixI 'False)
          (S1
             ('MetaSel
                'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy)
             (Rec0 Char)
           :*: S1
                 ('MetaSel
                    'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy)
                 (Rec0 Int)))
       x

D1, C1, S1 は M1 の特殊化で、コンストラクタの情報です。 Rec0 は K1 の特殊化で、中にフィールド内の情報を保持しています。 :*: によってペア (Char, Int) の構造が保存されている様子が伝わるでしょうか。

直和の場合も見てみましょう。

Prelude GHC.Generics> :t from ( (Just 'x') :: Maybe Char )
from ( (Just 'x') :: Maybe Char )
  :: D1
       ('MetaData "Maybe" "GHC.Base" "base" 'False)
       (C1 ('MetaCons "Nothing" 'PrefixI 'False) U1
        :+: C1
              ('MetaCons "Just" 'PrefixI 'False)
              (S1
                 ('MetaSel
                    'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy)
                 (Rec0 Char)))
       x

Nothing はフィールドが無いコンストラクタなので U1 が使われています。 :+: によって Just と Nothing の直和の構造が保存されている様子が伝わるでしょうか。

このように、Generic Programming を利用すると、 代数的データ型を直接操作する処理を書く代わりに、 Rep a x を操作する処理を書いておいて、 適切に from および to で変換することで、 任意の代数的データ型に対する汎用的な操作を書くことが可能となります。

GHC Generic Programming がどのように実現されているのかの理解の助けになればと思い、この記事を書いてみました。

ランキング参加中
Haskell