GHC.Genericsを利用したgeneric programming
Haskellとgeneric programmingに関してここしばらく調べており、GHC.Generics パッケージの提供する機能が便利だなと思ったのでまとめてみました。
実際のコードはgithubのリポジトリに配置しています。
1. Generic programming
Generic programming - Wikipediaでは以下のように述べられています。
Generic programming is a style of computer programming in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as patameters.
この定義を少し噛み砕いて日本語にすれば、「データ型を抽象化して関数、メソッド、データ構造等を実装するプログラミング手法」と言えるかなと思います。
例えばJavaではgeneric programmingを扱う機能はGenericsと呼ばれており、一例として以下のよう型パラメータTを持つクラス(Container)を書くことができます。
import java.util.Arrays;
public class GenericsSample {
public static void main(String[] args) {
Container<String> containerStr = new Container<>("Alice");
System.out.println(
containerStr.add(new Container<>("Bob"))
);
Container<Integer> containerInt = new Container<>(1);
System.out.println(
containerInt.add(new Container<>(2).add(new Container<>(3)))
);
}
}
// `T` in `Container<T>` is the type parameter.
class Container<T> {
private Object[] elems;
public Container(T elem) {
this.elems = new Object[]{elem};
}
private Container(T[] elems) {
this.elems = elems;
}
public Container<T> add(Container<T> other) {
final int newLen = this.length() + other.length();
Object[] newElems = new Object[newLen];
for (int i = 0; i < this.length(); i++) {
newElems[i] = this.elems[i];
}
for (int i = 0; i < other.length(); i++) {
newElems[i+this.length()] = other.elems[i];
}
return new Container<T>((T[])newElems);
}
public int length() {
return this.elems.length;
}
@Override
public String toString() {
return String.format("Container {elems = [%s]}",
Arrays.stream(elems).filter(s -> s != null)
.map(s -> s.toString()).reduce((acc,s) -> acc + "," + s)
.orElse(""));
}
}
ContainerクラスはいわゆるListを単純化したものを想定して定義しました。
Containerはある型に対する任意長の配列を持ち、それに対するインタフェースを提供しますが、特定のデータ型に依存するような(特定のデータ型に対してしか定義できないような)メソッドは持ちません。
そのためContainerクラスが扱う型を抽象化し、インスタンス生成時にパラメータとして具体的な型を受け取ることで、同一のクラス定義からStringを扱うContainerであるContainer<String>型、Integerを扱うContainer<Integer>型のオブジェクトを生成しています。
ちなみにmain関数の実行結果は以下のようになります。
Container {elems = [Alice,Bob]}
Container {elems = [1,2,3]}
2. 型変数
上と同じことをHaskellでは型変数を使用して行うことができます。
> add x xs = x:xs
> :t add
add :: a -> [a] -> [a]
> add 1 . add 2 $ [3]
[1,2,3]
> add 'a' . add 'b' $ ['c']
"abc"
型変数はHaskellが提供する素晴らしい機能ですが、ときにはより抽象化した形で関数の実装を行いたいと思う場合があります。
こういった場合によく挙げられている例としてSerializableという型クラスがあるので、ここでもそれを使用しようと思います。Serializable型クラスのインスタンスとなったデータ型ではbit列との相互変換を行えることが保証されます。
data Bit = I | O
deriving (Show, Eq)
class Serializable a where
serialize :: a -> [Bit]
deserialize :: [Bit] -> Maybe (a, [Bit]) -- (deserialized object, remain bits)
Serializableの簡単な例としてFruitデータ型とそのSerializableインスタンスを定義します。Fruit型は4種の単純な値コンストラクタから定義されるデータ型であるため、シリアル化された形式としては1, 01, 001, 0001という形としました。
data Fruit = Apple | Banana | Grape | Orange
deriving (Show, Eq)
instance Serializable Fruit where
serialize Apple = [I]
serialize Banana = [O,I]
serialize Grape = [O,O,I]
serialize Orange = [O,O,O,I]
deserialize (I:xs) = Just (Apple, xs)
deserialize (O:I:xs) = Just (Banana, xs)
deserialize (O:O:I:xs) = Just (Grape, xs)
deserialize (O:O:O:I:xs) = Just (Orange, xs)
deserialize _ = Nothing
> serialize Apple
[I]
> serialize Banana
[O,I]
> deserialize [I] :: Maybe (Fruit, [Bit])
Just (Apple,[])
> deserialize [O,I] :: Maybe (Fruit, [Bit])
Just (Banana,[])
もう少し複雑な例としてTree構造のデータに対してもSerializableを定義してみます。
{-# LANGUAGE ScopedTypeVariables #-}
data Tree a = Node (Tree a) (Tree a) | Leaf a
deriving (Show, Eq)
instance (Serializable a) => Serializable (Tree a) where
serialize (Node left right) = [I] ++ serialize left ++ serialize right
serialize (Leaf a1) = [O] ++ serialize a1
deserialize (I:xs) = do (l, remain1) <- deserialize xs
(r, remain2) <- deserialize remain1
return (Node l r, remain2)
deserialize (O:xs) = do (x, remain) <- deserialize xs :: Maybe (a, [Bit])
return (Leaf x, remain)
> let tree1 = Node (Node (Leaf Apple) (Leaf Banana)) (Node (Node (Node (Leaf Grape) (Leaf Orange)) (Leaf Apple)) (Leaf Banana))
> serialize tree1
[I,I,O,I,O,O,I,I,I,I,O,O,O,I,O,O,O,O,I,O,I,O,O,I]
> deserialize . serialize $ tree1 :: Maybe (Tree Fruit, [Bit])
Just (Node (Node (Leaf Apple) (Leaf Banana)) (Node (Node (Node (Leaf Grape) (Leaf Orange)) (Leaf Apple)) (Leaf Banana)),[])
以上のように与えられたデータ型に対してSerializableのインスタンスを定義することが可能ですが、よく見るとSerializableインスタンスは一定のルールに従えば機械的に定義できそうだということがわかります。
data Foo = A | B という直和型に対してはそれぞれの値コンストラクタで違うbit列を対応させればよく、一例として上記のFruit型のように左の値コンストラクタから順番にI, OI, OOI, … のように割り振ることができます。
またNode (Tree a) (Tree a)のような直積型data Bar = Bar B Cに関しては、B, Cをserializeしたものを左から順番に連結すればよく、deserializeもその逆だと思えばいけそうです。
このように具体的なデータ型を指定しなくても代数的に構成されたデータ型であれば一般化して関数を定義することができる、という場合に役に立つのがGHC.Genericsパッケージとなります。
3. GHC.Generics
GHC.Genericsパッケージの主な役割は任意の代数的データ型を表現するための型クラス、データ型を提供することだと言えると思います。
GHC.Genericsは主要なデータ型として以下の6つを定義しています。
data V1 p -- lifted version of Empty
data U1 p = U1 -- lifted version of ()
data (:+:) f g p = L1 (f p) | R1 (g p) -- lifted version of Either
data (:*:) f g p = (f p) :*: (g p) -- lifted version of (,)
newtype K1 i c p = K1 { unK1 :: c } -- a container for a c
newtype M1 i t f p = M1 { unM1 :: f p } -- a wrapper
また型クラスGenericを定義しています。ここでのRep aが抽象化されたデータ型で、これは上の6つの型を使用して表現されます。
class Generic a where
type family Rep a :: * -> * -- representation of the data a
from :: a -> Rep a x
to :: Rep a x -> a
{-# MINIMAL from, to #-}
-- Defined in ‘HC.Generics
これらを使用したgeneric programmingの手順は、
前提:
- 代数的データ型一般に対して定義できる型クラス
Xがある (e.g.Serializable) - 実際に型クラス
Xのinstanceとしたいユーザ定義のデータ型aがある (e.g.Tree)
- ユーザ定義のデータ型
aをGenericのinstanceとするRep aが型aを代数的な構造に基づいて抽象化した型となるGenericのinstanceとなることで、aとRep aとの相互変換が可能なことが保証される
Repを構成する上記6つのデータ型をXのinstanceとする
となります。aがRep aに抽象化でき、そのRep aがXのinstanceとなるので、型aにserializeが定義可能になるという感じです。説明はイマイチかもしれませんが、実際に見てみればすぐに納得できると思います。
4. GenericなSerializableの実装
この先では引き続きSerializableを例として、GHC.Genericsによるgeneric programmingの流れをおさえてみたいと思います。
4-1. 型クラス Genericのinstance実装
まずはserializeしたいユーザ定義型をGenericのinstanceとするのですが、実はこれはとても簡単でデータ型定義にderiving (Generic)を付け足し、DeriveGenericGHC拡張を有効化するだけになります。
例えばTreeの場合ですと以下のようになります。
{-# LANGUAGE DeriveGeneric #-}
data Tree a = Node (Tree a) (Tree a) | Leaf a
deriving (Show, Eq, Generic)
この状態でGHCi起動時に-ddump-derivオプションを渡すと、対象ソースのロード時に自動導出されたtype Rep aの定義を確認することができます。 (見づらいのでパッケージ名は省略しています)
> stack ghci --ghci-options -ddump-deriv
> :l src/Tiqwab/Generic/Tree.hs
type Rep (Tree a_a3oz) = D1 ('MetaData "Tree" "Serializable" "main" 'False)
(C1 ('MetaCons "Node" 'PrefixI 'False)
(S1 ('MetaSel 'Nothing
'NoSourceUnpackedness
'NoSourceStrictness
'DecidedLazy)
(Rec0 (Tree a_a3oz))
:*:
S1 ('MetaSel 'Nothing
'NoSourceUnpackedness
'NoSourceStrictness
'DecidedLazy)
(Rec0 (Tree a_a3oz)))
:+:
C1 ('MetaCons "Leaf" 'PrefixI 'False)
(S1 ('MetaSel
'Nothing
'NoSourceUnpackedness
'NoSourceStrictness
'DecidedLazy)
(Rec0 a_a3oz)))
ここでD1, C1, S1, Rec0といったデータ型は以下のように定義されています。
type D1 = M1 D
type C1 = M1 C
type S1 = M1 S
type Rec0 = K1 R
ということで表示されたRep (Tree a)が上記の6つのデータ型を使用して定義されていることがわかります (M1 DやK1 RのDやRに関してはそれぞれM1, K1の種分けをしたいというだけで文字自体には意味があるわけではないようです)。
データ型の細かい内容もhackageがわかりやすいのでそちらを参照なのですが、最初の認識としては
D1,C1,S1はデータ型、コンストラクタ、フィールドに対応し、それぞれメタデータを持つRec0は実際のフィールドのwrapperになっている- 直和を表すために
:+: - 直積を表すために
:*:
という程度を掴んでいれば、簡単な実装には問題無いのではと思います。
4-2. 抽象化されたデータ型に対するinstance実装
一番はじめにSerializable型クラスの定義として以下を与えました。
class Serializable a where
serialize :: a -> [Bit]
deserialize :: [Bit] -> Maybe (a, [Bit]) -- (deserialized object, remain bits)
今度は抽象化のためのデータ型(Repを構成するデータ型)に対してシリアル化処理を定義するためにSerializable'型クラスを作成します。説明では単純化のためserializeに対応する関数のみの実装とし、deserialize側は省略しています (コード上では両者実装しています)。
class Serializable' f where
serialize' :: f a -> [Bit]
もとのSerializable型クラスとは違い、パラメータfのkindが* -> *であることに注意です。これはV1, M1といった抽象化のためのデータ型が共通して持つ最後のパラメータpによるもののようですが、実際に処理の中で使用されるものではないのであまり気にしない方が良さそうです。
そしてSerializable'のinstanceの実装は以下のようになります。
{-# LANGUAGE TypeOperators #-}
instance Serializable' V1 where
serialize' x = undefined
instance Serializable' U1 where
serialize' x = []
instance (Serializable' f, Serializable' g) => Serializable' (f :+: g) where
serialize' (L1 x) = I : serialize' x
serialize' (R1 x) = O : serialize' x
instance (Serializable' f, Serializable' g) => Serializable' (f :*: g) where
serialize' (f :*: g) = serialize' f ++ serialize' g
instance (Serializable c) => Serializable' (K1 i c) where
serialize' (K1 x) = serialize x
instance (Serializable' f) => Serializable' (M1 i t f) where
serialize' (M1 x) = serialize' x
この実装の解説もhackageがとても親切なのですが、まとめると
V1が渡されたらundefinedとするdata Fooのような場合、V1が使用される
U1に対しては空のlistを返すdata Foo = Foo | Barのようなフィールドを持たない値コンストラクタに対し使用される
:+:はSerializableのTree実装で見たような直和の形式:*:はSerializableのTree実装で見たような直積の形式K1はwrappingしているデータ型に対してserializeするserialize'ではないことに注意- e.g.
Leaf aの場合のaをserializeする
M1はwrappingしているデータ型に対してserialize'する
のようになります。
次にもとのSerializable型クラスの定義をSerializable'を使用したものに変更します。
{-# LANGUAGE DefaultSignatures #-}
class Serializable a where
serialize :: a -> [Bit]
default serialize :: (Generic a, Serializable' (Rep a)) => a -> [Bit]
serialize x = serialize' (from x)
DefaultSignaturesGHC拡張により、型クラス定義内部にdefault実装を書くことができ、型が合えばユーザがserializeを実装しなくてもdefault実装(ここではserialize x = serialize' (from x))が使われるようになります。
これでGenericのinstanceとした任意のデータ型に対してserialize処理を行うことができるようになりました。最後にDeriveAnyClassGHC拡張を有効化し、ユーザ定義の型に対してSerializableを導出できるようにしておきます。
{-# LANGUAGE DeriveAnyClass #-}
data Fruit' = Apple' | Banana' | Grape' | Orange'
deriving (Show, Eq, Generic, Serializable)
data Tree' a = Node' (Tree' a) (Tree' a) | Leaf' a
deriving (Show, Eq, Generic, Serializable)
新規に定義したFruit'、Tree'は明示的なSerializableのinstance定義は持ちませんが、GHC.Genericsのパワーにより以下のようにserialize, deserializeを行うことができます (下調べが足りなかったのですが、型を表現するときの直和の扱い方が違うために最初に手で定義した実装とderivingさせたものでシリアル化したbit列が異なってしまっています。本質的なことではありませんが…)。
> serialize Apple'
[I,I]
> serialize Banana'
[I,O]
> deserialize [I,I] :: Maybe (Fruit', [Bit])
Just (Apple',[])
> deserialize [I,O] :: Maybe (Fruit', [Bit])
Just (Banana',[])
> let tree = Node' (Node' (Leaf' Apple') (Leaf' Banana')) (Node' (Node' (Node' (Leaf' Grape') (Leaf' Orange')) (Leaf' Apple')) (Leaf' Banana'))
> serialize tree
[I,I,O,I,I,O,I,O,I,I,I,O,O,I,O,O,O,O,I,I,O,I,O]
> deserialize . serialize $ tree :: Maybe (Tree' Fruit', [Bit])
Just (Node' (Node' (Leaf' Apple') (Leaf' Banana')) (Node' (Node' (Node' (Leaf' Grape') (Leaf' Orange')) (Leaf' Apple')) (Leaf' Banana')),[])
5. その他
以上でGHC.Genericsの提供する機能の7割程度はカバーできるのではないかと思うのですが、hackageを見る限り他には以下のような内容が含まれるようです。
Generic1class- Representation of unlifted types
これらに関しては理解が足りていないのでここでは触れられませんが、Generic1に関してはgeneric-derivingパッケージが理解に役立ちそうです。
Summary
GHC.GenericsはHaskellでgeneric programmingを行う上で強力な機能- 自分で定義した型クラスでderivingできるのは気持ち良い