Chanomic Blog

PureScriptメモ - Generics

(last modified:
)

tags:

categories:

purescript-generics-repパッケージを使ってGenericなSerializer型クラスを作った。以下はそのメモ。

準備

プロジェクトを作成。

$ spago init

Arrayを使うので、パッケージをインストールしてsrc/Main.pursにimport文を書き込んでいく。 本記事の本命であるgenerics-rep入れる。

$ spago install arrays
$ spago install generics-rep


import Data.Array ((:))

REPLで色々実験するので、あらかじめ起動しておく。

$ spago repl
> import Main

以降はsrc/Main.pursに色々書き足していく。REPLで:r(もしくは:reload)とコマンドを打てばモジュールが再読み込みされるので、src/Main.pursを書き換える度にこのコマンドを打つと良い。

Serializer

そもそもSerializerとは何か。ここでは単に「データをビット列に変換するもの」程度の意味で捉えれば良い。 厳密にはJSONなどの階層を持つデータを，文字列などの平坦なデータに変換するという意味合いとしてシリアライズ(直列化)という言葉を使う。実際、本記事では最終的に木構造をシリアライズする。

まずビットは次のように定義する。

data Bit = O | I

instance showBit :: Show Bit where
  show O = "O"
  show I = "I"

Serializer型クラスを以下のように定義する。

class Serializer a where
  serialize :: a -> Array Bit

試しに適当な型をつくり、それをSerializer型クラスのインスタンスにしてみる。

data Person = Alice | Bob | Carol

instance serializerUser :: Serializer Person where
  serialize Alice = [ I ]
  serialize Bob   = [ O, I ]
  serialize Carol = [ O, O, I ]

余談。今回はデシリアライザは実装しないので、シリアライズしたデータを同じ形に戻せるかは考えない。このあたりは情報理論の授業で「一意復号化可能性」などをやった気がするけど、忘れてしまった。

REPLで実験してみる。

> serialize Alice
[I]

> serialize Bob
[O,I]

> serialize Carol
[O,O,I]

Tree型をSerializer型クラスのインスタンスにする(素朴な方法)

2分木のデータ構造であるTree型を作る。

data Tree a = Node (Tree a) (Tree a) | Leaf a

instance serializerTree :: Serializer a => Serializer (Tree a) where
  serialize (Node l r) = I : (serialize l <> serialize r)
  serialize (Leaf x) = O : serialize x

テスト用のデータを作ってREPLでシリアライズしてみる。

tree :: Tree Person
tree = Node (Node (Leaf Alice) (Leaf Bob)) (Leaf Carol)

> serialize tree
[I,I,O,I,O,O,I,O,O,O,I]

一般化

さて、3分木なら例えば次のようにSerializer型クラスのインスタンスにできる。

data Tree a = Node (Tree a) (Tree a) (Tree a) | Leaf a

instance serializerTree :: Serializer a => Serializer (Tree a) where
  serialize (Node n1 n2 n3) = I : (serialize n1 <> serialize n2 <> serialize n3)
  serialize (Leaf x) = O : serialize x

木に限らず、有名な型については例えば次のようにインスタンスにできるだろう。

instance serializerMaybe :: Serializer a => Serializer (Maybe a) where
  serialize (Just x) = I : serialize x
  serialize Nothing  = []

instance serializerEither :: (Serializer a, Serializer b) => Serializer (Either a b) where
  serialize (Left x)  = I : serialize x
  serialize (Right y) = O : serialize y

instance serializerList :: (Serializer a) => Serializer (List a) where
  serialize (Cons x xs) = I : serialize x <> serialize xs
  serialize Nil  = []

3つの値を持つデータ型なら例えば次のようにできる。

data T0 a b c = One a b | Two b | Three c b a

instance serializerT0 :: (Serializer a, Serializer b, Serializer c) => Serializer (T0 a b c) where
  serialize (One x y) = I : (serialize x <> serialize y)
  serialize (Two x)   = O : I : serialize x
  serialize (Three x y z) = O : O : I : (serialize x <> serialize y <> serialize z)

上の例はアドホックなものであり、実装そのものに共通点はない。ただし、実装する上での気持ち「データの値ではなくデータの表現に注目する」では共通している。 ここでいう表現というのは、たとえば3つ目の例でいうと、

OneとTwoとThreeという値を持ち，

がT0の持つ表現である。

そのような、データの表現に応じてシリアライズの仕方を実装することができれば、いちいちMaybeやEitherやT0など個別にSerializer型クラスのインスタンス宣言を書かずに済む。 それを可能にするのが、purescript-generics-repパッケージである。これは、データ型の持つ表現そのものを型にする手段を提供する。

Data.Generic.Rep

モジュールをインポートする。

import Data.Generic.Rep

Generic型クラス

Generic型クラスのインスタンスを導出させることで、Treeの表現が生成される。アンダーバーはコンパイラが自動で埋めてくれる。

derive instance genericTree :: Generic (Tree a) _

ドキュメントによると、Generic型クラスは次のように定義されている。

class Generic a rep | a -> rep where
  to :: rep -> a
  from :: a -> rep

repが、型aの表現を表す(repというのは、恐らくrepresentation(表現)の略)。fromを使えば、aの表現が得られる。REPLでTreeの表現の型を確認してみる。

> import Data.Generic.Rep
> :t from tree
Sum (Constructor "Node" (Product (Argument (Tree Person)) (Argument (Tree Person)))) (Constructor "Leaf" (Argument Person))

なので実際には、アンダーバーのところを埋めると次のようになるようだ(ただし、必ずアンダーバーでなければならないようで、これはコンパイルエラーになる)。

derive instance genericTree
  :: Generic
       (Tree a)
       (Sum (Constructor "Node" (Product (Argument (Tree a))
                                         (Argument (Tree a))))
            (Constructor "Leaf" (Argument a)))

表現の構成要素

表現が構成する型は次の4つ。

data Sum a b = Inl a | Inr b
data Constructor (name :: Symbol) a = Constructor a
data Product a b = Product a b
data Argument a = Argument a
data NoConstructors
data NoArguments = NoArguments

であることを踏まえると、

(Sum (Constructor "Node" (Product (Argument (Tree a))
                                  (Argument (Tree a))))
     (Constructor "Leaf" (Argument a)))

は、次のように読める：この型は2つのコンストラクタがあることを表現している。1つ目の値コンストラクタ名はNodeで、その引数としてTree a型の値を2つ持つ。 2つめの値コンストラクタ名はLeafで、その引数としてa型の値を1つ持つ。

ちなみにderiveを使わないでTreeについてのインスタンス宣言をすると次のようになる。勿論deriveを使えばいい話なので、普通こんなことはやらない。

instance genericTree
  :: Generic
       (Tree a)
       (Sum (Constructor "Node" (Product (Argument (Tree a))
                                         (Argument (Tree a))))
            (Constructor "Leaf" (Argument a)))
  where
    to (Inl (Constructor (Product (Argument l) (Argument r)))) = Node l r
    to (Inr (Constructor (Argument x))) = Leaf x
    from (Node l r) = Inl (Constructor (Product (Argument l) (Argument r)))
    from (Leaf x) = Inr (Constructor (Argument x))

応用例：Showクラスのインスタンスにする

PureScriptでは、Haskellと違って、Show型クラスのインスタンス導出ができない(参考)。しかし代わりに、Generic型クラスを利用すれば、導出と同じようなことができる。

まずは、関連モジュールをインポートする。

import Data.Generic.Rep.Show

試しに、Person型をShow型クラスのインスタンスにしてみる。

derive instance genericPerson :: Generic Person _
instance showPerson :: Show Person where
  show x = genericShow x

genericShowは、Personの表現をもとに値を文字列に変換する関数。単にPersonをGeneric型クラスのインスタンスにするだけで利用できる。

> Alice
Alice

> Bob
Bob

> Carol
Carol

Treeも同様にShow型クラスのインスタンスにできる。

instance showTree :: Show a => Show (Tree a) where
  show x = genericShow x

> tree
(Node (Node (Leaf Alice) (Leaf Bob)) (Leaf Carol))

Data.Generic.Rep.Showのコードを読んでみると、どうやって表現を使って実装するのかがよく分かる。

補足：Showクラスのインスタンス化に関する注意点

次のように書くと、show関数を呼び出した際に実行時エラー：Maximum call stack size exceeded起こす。

instance showTree :: Show a => Show (Tree a) where
  show = genericShow

show x = genericShow xもshow = genericShowも本質的には同じ意味なのに、前者はうまくいき、後者は実行時エラーを吐くのはおかしい。

この問題についてgenerics-repのissueやpurescriptのissueでも上がっている。 後者のissueではClosedになってしまっているようだし、修正されないのだろうか。単にshow x = genericShow xと書けば防げる問題なので、そこまで大した問題ではないのかもしれないが…。

本題：Tree型をSerializer型クラスのインスタンスにする(表現を利用する方法)

Data.Generic.Rep.Showのコードの手法を真似て、次のように作る。

そこで、Serializer'型クラスを作る。

class Serializer' a where
  serialize' :: a -> Array Bit

表現に関連する部分は全てSerializer'型クラスのインスタンスにする。最後のArgumentだけ、引数に普通の型が含まれているため、型クラス制約がSerializer'ではなくSerializerであることに注意。

instance serializerSum :: (Serializer' a, Serializer' b) => Serializer' (Sum a b) where
  serialize' (Inl x) = I : serialize' x
  serialize' (Inr x) = O : serialize' x

instance serializerConstructor :: (Serializer' a) => Serializer' (Constructor name a) where
  serialize' (Constructor x) = serialize' x

instance serializerProduct :: (Serializer' a, Serializer' b) => Serializer' (Product a b) where
  serialize' (Product x y) = serialize' x <> serialize' y

instance serializerNoArguments :: Serializer' NoArguments where
  serialize' _ = []

instance serializerArgument :: (Serializer a) => Serializer' (Argument a) where
  serialize' (Argument x) = serialize x

最後に、serialize'を使ってTreeをSerializer型クラスのインスタンスにする。前に作成したインスタンス宣言は消す。

instance serializerTree :: (Serializer a) => Serializer (Tree a) where
  serialize x = serialize' $ from x

素朴に作った場合と同じ結果が出ている。

> serialize tree
[I,I,O,I,O,O,I,O,O,O,I]

Tree型の値そのものに注目せずにSerializerが実装できたことに注目してほしい。Tree aに限らず、例えば型T0 a b cがあったとき、

という2つの条件が揃えば、T0はシリアライズできることになる。

補足：Tree以外の型をSerializer型クラスのインスタンスにする

自作の型なら、容易にSerizlizerのインスタンスにできる。

data T0 a b c = One a | Two b | Tree c

derive instance genericT0 :: Generic (T0 a b c) _

instance serializerT0 :: (Serializer a, Serializer b, Serialier c) => Serializer (T0 a b c) where
  serialize x = serialize' $ from x

Maybe aに関しては特別にData.Generic.Repでインスタンス宣言がなされているため、次のようにSerializerのインスタンスにできる。

instance serializerTree :: (Serializer a) => Serializer (Tree a) where
  serialize x = serialize' $ from x

別モジュールで定義された型を、Genericを使ってSerializerのインスタンスにすることはできない。 なぜなら、今回の場合「Main外で定義された型」に対して「Main外で定義された型クラスGeneric」のインスタンス宣言をすることになり、これはOrphan instanceに当たるからだ PureScriptではOrphan instanceは禁止されている(参考)。

この問題を解決するためにぱっと思いついた方法は、以下のようなもの。以下はEitherをSerializer型クラスのインスタンスにしている。Eitherの別表現としてEither'を用意する。 EitherはMain外のモジュールで定義されているため、直接Generic型インスタンスにすることはできない。しかし、Either'はGenericにすることはできる。 よって、一旦Either'を経由してEitherのSerializerインスタンス宣言をすることができる。

data Either' a b = Left' a | Right' b

fromEither :: forall a b. Either a b -> Either' a b
fromEither (Left x) = Left' x
fromEither (Right x) = Right' x

derive instance genericEither' :: Generic (Either' a b) _

instance serializerEither :: (Serializer a, Serializer b) => Serializer (Either a b) where
  serialize x = serialize' $ from  $ fromEither x

ちなみに、最近EitherをGenericのインスタンスにする動きあるようだ。

参考文献

本記事を書くに当たって参考にした文献を挙げておく。

Haskell方面

PureScriptはHaskellの影響を受けているので、Haskellの資料が参考になることは結構ある。ただし、構文や型名、パッケージ名など違いがあるので、それらについては根気強く調べる必要がある。

PureScript方面

あまり見つからなかった…。