Subscribed unsubscribe Subscribe Subscribe

[Haskell] 普通のtype classesとmulti-parameter type classesとfunctional dependenciesとtype families

multi-parameter type classes周辺の理解があやふやなままだったので、Type classes: exploring the design spaceType Classes with Functional Dependencies* (PDF)Type Cheking with Open Type Functions (PDF)あたりをわかる範囲で読んでみた。

1つめの論文はMPTCのmulti-parameter type classes (MPTC) の概要とその適用例について紹介し、2本目ではMPTCの問題点と、それを解決する ための手法としてfunctional dependencies (fundeps) が提案されている。最後の3本目はfundepsと似たような機能をもたらすtype familiesについて書かれている。

というわけで、せっかくなのでまとめてみた。間違いがあったら指摘していただけると助かる。

このエントリについて

このエントリはLiterate Haskell形式になっているので、コピペしてインタプリタからロードするとそのまま実行できる。

> {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, TypeFamilies, FlexibleInstances, FlexibleContexts #-}
> import Data.ByteString (ByteString)
> import qualified Data.ByteString as BS
> import Data.Set (Set)
> import qualified Data.Set as Set
> import Data.Word

例題: Collectsクラス

これら論文では、例題としてコレクションクラスCollectsを取り上げている。このCollectsクラスは次の3つのメソッドを持っている。

  1. 空の集合を返すempty
  2. 集合に要素を一つ追加するinsert
  3. 集合にある要素が含まれるか判定するmember

実に一般的なインタフェース。このCollectsクラスのインスタンスとしては、リストや木、ビット集合とかハッシュテーブルなど幅広いデータ 構造が考えられる。ではこのCollectsクラスをどう実装するかというのが今回の課題。

普通のクラス

普通の(MPTCでない)型クラスで定義する方法がType classes: exploring the design spaceの2.2節に載っている。この方法はChris OkasakiのPurely Functioal Data Structuresのサンプルコードでも使われている。

-- Standard Type Classes
class Collects_TC c where
  empty_TC  :: c e
  insert_TC :: e -> c e -> c e
  member_TC :: e -> c e -> Bool

一番安直なインスタンス宣言としてリストを考える。

instance Collects_TC [] where
  empty_TC  = []
  insert_TC = (:)
  member_TC = elem

上のコードはコンパイルできない。なぜなら、member_TCメソッドの実装に使われているelem関数の型は

elem :: (Eq a) => a -> [a] -> Bool

である一方、member_TCにはEqという制約がない。member_TCには陰にuniversal quantifierがついているのと同じことになる。この問題を回避 するには、member_TCメソッドシグネチャにEq eを追加する。

-- Standard Type Classes
class Collects_TC c where
  empty_TC  :: c e
  insert_TC :: e -> c e -> c e
  member_TC :: Eq e => e -> c e -> Bool

これでコンパイルが通るようなる。では、同様に標準ライブラリに含まれるData.SetをCollects_TCのインスタンスにするにはどうしたらよいか。

> instance Collects_TC Set where
>   empty_TC  = Set.empty
>   insert_TC = Set.insert
>   member_TC = Set.member

実装に用いたSet.insertとSet.memberの型は次のようになっている。

Set.insert :: (Ord a) => a -> Set a -> Set a
member :: (Ord a) => a -> Set a -> Bool

従って、このインスタンスを定義するには再び、Collects_TCクラスを変更する必要がある。

> -- Standard Type Classes
> class Collects_TC c where
>   empty_TC  :: c e
>   insert_TC :: Ord e => e -> c e -> c e
>   member_TC :: (Eq e, Ord e) => e -> c e -> Bool

このような変更は望ましくない。なぜなら、

  • 制約の厳しいインスタンス宣言をするごとにclass定義を変更する必要があり
  • 本来必要のない制約を強いている

からである。

これを解決するためにMPTCを用いる。

multi-parameter type classesを使う

MPTCを使った実装は、Type classes: exploring the design spaceにも、Type Classes with Functional Dependencies* (PDF)にも載っている。

素直に実装するとこうなるだろう。

> -- MPTCs
> class Collects_MPTC e c where
>   empty_MPTC  :: c
>   insert_MPTC :: e -> c -> c
>   member_MPTC :: e -> c -> Bool
> 
> instance Eq e => Collects_MPTC e [e] where
>   empty_MPTC  = []
>   insert_MPTC = (:)
>   member_MPTC = elem
>
> instance (Eq e, Ord e) => Collects_MPTC e (Set e) where
>   empty_MPTC  = Set.empty
>   insert_MPTC = Set.insert
>   member_MPTC = Set.member

class宣言における型変数が2つになったことで、要素への制約条件(Eq eやOrd e)をinstance宣言の先頭に追い出すことができるようになった 。

このコードは一見正しい定義に見えるが、問題がある。

ひとつは、empty_MPTCの型が曖昧(ambiguous)なこと。empty_MPTCの型はempty_MPTC :: Collects_MPTC e ce => ceとなってい て、=>の左辺にあるeが右辺には出てこない。Haskellでは、オーバーローディングの理論的な基礎により、このような曖昧な型は弾かれてしまうらしい。

この問題はCollects_MPTCクラスからempty_MPTCメソッドを外すことで回避できるが、それでもまだ別に問題がある。下のような関数f_MPTCとg_MPTCを考える。

> f_MPTC x y c = insert_MPTC x $ insert_MPTC y c
> g_MPTC c     = f_MPTC True 'a' c

この関数f_MPTCとg_MPTCの型はそれぞれ次のように推論される。

> f_MPTC :: (Collects_MPTC a c, Collects_MPTC b c) => a -> b -> c -> c
> g_MPTC :: (Collects_MPTC Bool c, Collects_MPTC Char c) => c -> c

これでは困る。f_MPTCを見てみると、2つのinsertは同じ型の要素の挿入であるはずなのに、推論結果はaとbとなり別の型の要素となっている。さらにg_MPTCを見ると、一つの集合に別の型の要素をinsertしているにもかかわらず、型検査は通りコンパイルできてしまう。

このことから、何らかの方法を用いて

  1. 型の曖昧さをなくし
  2. 正しい型へと推論し
  3. 型エラーを早期に発見できる

ように改善する必要があることがわかる。

MPTCs + constructor classesを使う

MPTCではコレクションを表す型変数をcとしていたが、これをc eとする。定義は次のようになる。

> -- MPTC + Constructor Classes
> class Collects_CC e c where
>   empty_CC  :: c e
>   insert_CC :: e -> c e -> c e
>   member_CC :: e -> c e -> Bool
> 
> instance Eq e => Collects_CC e [] where
>   empty_CC  = []
>   insert_CC = (:)
>   member_CC = elem
>
> instance (Eq e, Ord e) => Collects_CC e Set where
>   empty_CC  = Set.empty
>   insert_CC = Set.insert
>   member_CC = Set.member
>
> f_CC x y c = insert_CC x $ insert_CC y c
> -- g_CC c     = f_CC True 'a' c -- type error!

この定義では、先の3つの問題点がすべて解決できる。

  1. empty_CCの型はempty_CC :: Collects_CC e c => c eとなり、曖昧さは無くなった
  2. insert_CCの型はinsert_CC :: Collects_CC e c => e -> e -> c e -> c eとなり、insertする要素が同一の型に推論されるよ うになった
  3. g_CCは意図通りコンパイルエラーに

しかし、今度は別の問題点が浮かび上がる。Collects_CCクラスはこれまで見てきたCollects_*クラスほど一般的ではない。これは、新たにByteStringをCollects_CCのインスタンスにしようとするときにわかる。ByteStringは[]やSetとは異なりtype constructorではなく、普通の型だか らである。これはghciセッションで種(kind)を調べればわかる。

Prelude Data.Set Data.ByteString> :k []
[] :: * -> *
Prelude Data.Set Data.ByteString> :k Set
Set :: * -> *
Prelude Data.Set Data.ByteString> :k ByteString
ByteString :: *

c eと表記される型cは* -> *という種を持っている必要がある。いくつかの例ではラッパークラスを作ることでこの問題を回避できるが、ByteStringでは回避できない問題である。

functional dependenciesを使う

上の問題も解決できる方法がある。その一つがfundeps。MPTCsの例を少し書き換えることになる。

> -- Functional Dependencies
> class Collects_FD e c | c -> e where
>   empty_FD  :: c
>   insert_FD :: e -> c -> c
>   member_FD :: e -> c -> Bool
> 
> instance Eq e => Collects_FD e [e] where
>   empty_FD  = []
>   insert_FD = (:)
>   member_FD = elem
> 
> instance (Eq e, Ord e) => Collects_FD e (Set e) where
>   empty_FD  = Set.empty
>   insert_FD = Set.insert
>   member_FD = Set.member
> 
> instance Collects_FD Word8 ByteString where
>   empty_FD  = BS.empty
>   insert_FD = BS.cons
>   member_FD = BS.elem

クラス宣言の|c -> eが意味するものは、型cが決まれば自動的にeが定まるということ。この依存関係を明示することで、MPTCsの時に起きた、型推論の曖昧さをなくしている。理論的な背景とか内部の実装は、論文をちゃんと読んでないのでわからない。

この実装だとfもgも意図したとおりに動く。

> f_FD x y c = insert_FD x $ insert_FD y c
> -- g_FD c     = f_FD True 'a' c -- type error!

type familiesを使う

fundepsと同じ機能をより関数的に書けるというらしいtype familiesを使ってみる。これはType Cheking with Open Type Functions (PDF)に書かれている。

> -- Type Families
> type family Elem c
> 
> class Collects_TF c where
>   empty_TF  :: c
>   insert_TF :: Elem c -> c -> c
>   member_TF :: Elem c -> c -> Bool
> 
> type instance Elem [e] = e
> 
> instance Eq c => Collects_TF [c] where
>   empty_TF  = []
>   insert_TF = (:)
>   member_TF = elem
> 
> type instance Elem (Set e) = e
> 
> instance (Eq e, Ord e) => Collects_TF (Set e) where
>   empty_TF  = Set.empty
>   insert_TF = Set.insert
>   member_TF = Set.member
> 
> type instance Elem ByteString = Word8
> 
> instance Collects_TF ByteString where
>   empty_TF  = BS.empty
>   insert_TF = BS.cons
>   member_TF = BS.elem

こちらもfundepsと同様にすべてが意図したとおりに動く。

> f_TF x y c = insert_TF x $ insert_TF y c
> -- g_TC c     = f_TF True 'a' c -- type error!

Functional dependencies versus type families and beyond (PDF)には、fundepsよりtype familiesの方が良さそうな感じで書いてあるが、詳しくは見ていないのでわからない。

まとめ

後半に進むにつれて雑なまとめになったけど、大まかにまとめると

  • MPTCsは各インスタンス間で異なる制約を、それぞれ分離して書くのに使える
  • MPTCsを素で使おうとすると、うまく型推論できずに使えない
  • そこで必要なのがfundepsとかtype families

という感じ。

あと雑感

  • どの論文もコレクション以外の別の使い方が書いてあるみたいなので後で読んでみたい
  • type familiesの利点とかだれか3行でまとめてないかなあ

などなど。

長らく謎のまま放置していた型クラス周りが、やっと少しわかってきてよかった。