総称クラス

この拡張の背後にある考えは"Derivable type classes", Ralf Hinze and Simon Peyton Jones, Haskell Workshop, Montreal Sept 2000, pp94-105で詳述されている。例を挙げればどういうものか分かるだろう。

  import Data.Generics

  class Bin a where
    toBin   :: a -> [Int]
    fromBin :: [Int] -> (a, [Int])
  
    toBin {| Unit |}    Unit	  = []
    toBin {| a :+: b |} (Inl x)   = 0 : toBin x
    toBin {| a :+: b |} (Inr y)   = 1 : toBin y
    toBin {| a :*: b |} (x :*: y) = toBin x ++ toBin y
  
    fromBin {| Unit |}    bs      = (Unit, bs)
    fromBin {| a :+: b |} (0:bs)  = (Inl x, bs')    where (x,bs') = fromBin bs
    fromBin {| a :+: b |} (1:bs)  = (Inr y, bs')    where (y,bs') = fromBin bs
    fromBin {| a :*: b |} bs	  = (x :*: y, bs'') where (x,bs' ) = fromBin bs
							  (y,bs'') = fromBin bs'

このクラス宣言は、toBinfromBinが任意のデータ型についてどのように動作するかを説明している。これを達成するために、単位、積、和のそれぞれの場合についての処理を与えている。これらはData.Genericsというライブラリモジュールで定義されている。

  data Unit    = Unit
  data a :+: b = Inl a | Inr b
  data a :*: b = a :*: b

これで、次のようにしてデータ型をBinのインスタンスにすることができる。

  instance (Bin a, Bin b) => Bin (a,b)
  instance Bin a => Bin [a]

つまり、単に「where」節を省略すれば良い。もちろん、where節を書いて、望むメソッドを再定義することもできる。

総称性を使う

総称性を使うには以下のものが必要である。

  • フラグとして、-XGenerics(拡張構文を有効にし、データ型毎の追加コードを生成する)と-package syb(Data.Genericsライブラリを利用可能にする)を使う。

  • sybパッケージのData.Genericsモジュールをインポートする。これによって、Unit:*::+:の各データ型がスコープに導入される。(これらの型に明示的に言及しないならインポートは必要ない。インスタンス宣言を行うだけの場合など)

論文からの変更点

型構築子:+:および:*:は中置記法で書かれることに注意。(実際、コロンで始まるあらゆる演算子列が型構築子として使えるようになった)。また、型構築子は論文そのままではない(1の代わりにUnit、など)。最後に、クラス宣言のパターンの構文で使われる括弧は「{|」と「|}」である。中括弧だけだと、右辺で使われる(こういう拡張が必要になるかもしれない)ときに曖昧になる。

用語と制約

用語。クラス宣言中の「総称デフォルトメソッド」とは、上のような型パターンを使って定義されたもののことである。「多相デフォルトメソッド」とは、Haskell 98式のデフォルトメソッドのことである。「総称クラス宣言」とは、少なくとも一つの総称デフォルトメソッドを含むクラス宣言のことである。

制約は以下の通り。

  • 残念ながら、構築子名とフィールドラベルに関するものはまだ実装していない。

  • 総称クラスのパラメタは一つでなければならない。総称的な多引数型クラスを書くことはできない。

  • あるデフォルトメソッドは、全部型パターンを使って定義するか、全部型パターンなしで定義するかのいずれかでなければならない。従って以下は不正である。

      class Foo a where
        op :: a -> (a, Bool)
        op {| Unit |} Unit = (Unit, True)
        op x               = (x,    False)
    

    一方、ある総称クラスについて、総称デフォルトメソッドと多相デフォルトメソッドの両方があるのは、全く問題ない。

  • 総称メソッド宣言の型パターンに現れる型変数は右辺全体に渡るスコープを持つ。従って下記は合法である。(型変数「p」を右辺の型シグネチャで使っていることに注意)

      class Foo a where
        op :: a -> Bool
        op {| p :*: q |} (x :*: y) = op (x :: p)
        ...
    
  • 総称デフォルトメソッドにおける型パターンは以下のいずれかの形を取らなければならない。

           a :+: b
           a :*: b
           Unit
    

    ここで「a」と「b」は型変数である。さらに、一つの型構築子(例えば:*:)についての型パターンは全て同じでなければならない。これは、同じ型変数を使わなければならないということである。したがって以下の例は非合法である。

      class Foo a where
        op :: a -> Bool
        op {| a :+: b |} (Inl x) = True
        op {| p :+: q |} (Inr y) = False
    

    あるクラスの異なるメソッドの間でも、やはり型パターンは相等しくなければならない。従って以下は非合法である。

      class Foo a where
        op1 :: a -> Bool
        op1 {| a :*: b |} (x :*: y) = True
    
        op2 :: a -> Bool
        op2 {| p :*: q |} (x :*: y) = False
    

    (この制約があるのは、ひとつの総称インスタンス宣言を作る際、特定の型構築子についての等式を全て集めるからである)

  • 総称メソッド宣言では、この三つの型構築子のそれぞれの場合について処理を与えなければならない。

  • 総称メソッドの型は、以下の型のみから構成されていなければならない。

    • 関数の矢印

    • 型変数

    • タプル

    • 型変数を含まない任意の型

    総称メソッドの型シグネチャの例である。

        op1 :: a -> Bool
        op2 :: Bool -> (a,Bool)
        op3 :: [Int] -> a -> a
        op4 :: [a] -> Bool
    

    ここで、op1、op2、op3は問題ないが、op4は拒否される。リストの中に型変数があるからである。

    この制約は実装上の都合によるものである。我々には、任意の型構築子について必要な双方向写像を実装する時間の余裕がない。Maybeやリストといった特定の型構築子を許されるようにするのは比較的簡単だろう。

  • 総称クラスのインスタンス宣言では、基本的には、総称テンプレートを基にして、コンパイラがメソッドを挿入する。しかし、これには以下の条件が必要である。

    • インスタンス型が単純(Haskell 98の通りに、型構築子を型変数に適用したもの)であること。

    • インスタンス型の構築子に、非ボックス化フィールドを持つものがないこと。

    (もちろん、これらは既にGHC拡張を使っている場合にのみ該当し得る)。また、明示的なコードで総称デフォルトメソッドを全て再定義することで、この規則に反する型にインスタンス宣言を与えることができる。

-ddump-derivオプションを使うと、総称宣言についてコンパイラが何をしているかの詳細を含んだ、理解困難な何かを表示することができる。

もう一つの例

最後に、私が少し気に入っている例を挙げる。

  class Tag a where
    nCons :: a -> Int
    nCons {| Unit |}    _ = 1
    nCons {| a :*: b |} _ = 1
    nCons {| a :+: b |} _ = nCons (bot::a) + nCons (bot::b)
  
    tag :: a -> Int
    tag {| Unit |}    _       = 1
    tag {| a :*: b |} _       = 1   
    tag {| a :+: b |} (Inl x) = tag x
    tag {| a :+: b |} (Inr y) = nCons (bot::a) + tag y