SetはFunctorである

Haskell Advent Calendar 2013 9日目です。

なぜSetはFunctorになっていないのか


Setを要素が重複しないデータ構造とします。Setはその性質のため、要素には比較出来ることが要求されます。Haskellで言うとEq制約です。まあ本来重複しないことだけを要求するならEq制約だけでいいはずですが、SetがOrd制約を要求しているのは効率の良い実装にするためでしょう。containersパッケージのData.Setはバランス二分木で実装されています。


本来SetはFunctorにすることが出来るはずです。しかし現状(GHC7.6.3)、SetはFunctorのinstanceとはなっていません。それはSetがその要素にOrd制約を要求することが原因となっています。一般にHaskellでよく用いられるFunctorは、その定義より、コンテナの要素について何も言及することが出来ません。

class  Functor f  where
    fmap        :: (a -> b) -> f a -> f b


試しにSetをFunctorにしようとしてみます。


containersパッケージはSetのmapを提供しており、以下の型を持っています。

Data.Set.map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

このmapは、Setの性質である「要素は重複しない」という性質を保ちます。

import qualified Data.Set as S
main = print $ S.map abs (S.fromList [-3,-2,-1,0,1,2,3]) -- fromList [0,1,2,3]

これをfmapにする形でSetをFunctorのinstanceにします。

import qualified Data.Set as S

instance Functor S.Set where
    fmap = S.map

すると以下の様に怒られます。

/Users/ruicc/works/sketch/set.hs:4:12:
    No instance for (Ord b) arising from a use of `S.map'
    Possible fix:
      add (Ord b) to the context of
        the type signature for fmap :: (a -> b) -> S.Set a -> S.Set b
    In the expression: S.map
    In an equation for `fmap': fmap = S.map
    In the instance declaration for `Functor S.Set'

fmapに(Ord b)を加えてはどうか?などと言ってきますが、それを加えたらFunctorがFunctorでなくなってしまいます。
FunctorやMonadは現在、型制約をうまく扱えるような定義になっていないのです。

Restricted Monad Problem


このSetをFunctorやMonadに出来ない問題は、Restricted Monad Problemとかなんとかと呼ばれ、以前から様々な解決法が提案されています。
コンテナの中身を型クラスに含めるものやTHでなんとかするもの、そしてConstraint Kindsを用いるものなどです。

Constraint Kinds


ConstraintKinds下では、Constraint周辺は以下の様に扱われます。

Ord :: * -> Constraint -- 型クラスの型コンストラクタのkind
() :: Constraint -- 空のConstraint
(,) :: Constraint -> Constraint -> Constraint -- Constraintの結合

ConstraintKindsプラグマはConstraintをモノイドのように扱えるようにしてくれるようです。具体的には以下の用な記述を可能にします。

f :: () => a -- これはプラグマ無くても書ける
g :: ((), ()) => a
h :: ((Ord a, Eq a), a ~ b) => a -> b

type familyと組み合わせると、Constraintに関する関数のようなものも記述出来ます。

type family Conj (a :: Constraint) (b :: Constraint) (c :: Constraint) :: Constraint
type instance Conj a b c = (a, b, c)

楽しげですね。
まあこのあたりは今は置いておきましょう。

Set Functor


Restricted Functor(RFunctor)を次の様に定義します。

{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE TypeFamilies #-}

import           GHC.Prim (Constraint)
import qualified Data.Set as S

class RFunctor f where
    type RSubCats f a :: Constraint
    type RSubCats f a = ()
    rfmap :: (RSubCats f a, RSubCats f b) => (a -> b) -> f a -> f b

するとそのインスタンスは次の様に定義出来ます。
例として[]とSetをインスタンスにします。

instance RFunctor [] where
    rfmap = map

instance RFunctor S.Set where
    type RSubCats S.Set a = (Ord a)
    rfmap = S.map

嬉しいことに[]の定義は既存のFunctorと全く変わりません。RFunctorのRSubCatsのデフォルトの定義を()としているためです。そのため、Setの様に要素に制限を付けたいときだけRSubCatsを定義すればいいことになります。

main = print $ rfmap abs (S.fromList [-2, -1, 0, 1, 2]) -- fromList [0,1,2]

SetがFunctorのインスタンスになったことにより、(r)fmapが使えるようになりました。
まあしかしこのままではS.mapをそのまま使っても全く変わりません。やはりモナドが欲しくなりますね。

Set Monad


Set Monadを定義します。
まずはRMonadです。RFunctorにを親クラスにします。RApplicativeを挟まなかったのは面倒だっただけです。

class RFunctor m => RMonad m where
    rreturn :: (RSubCats m a) => a -> m a
    rbind :: (RSubCats m a, RSubCats m b) => m a -> (a -> m b) -> m b

instance RMonad S.Set where
    rreturn = S.singleton
    m `rbind` f = S.unions $ map f (S.toList m)

Set Monadが定義出来ました。
重複した値が潰されるモナドの完成です。

main = do
    print $ (S.fromList [-2 .. 2 :: Int]) `rbind` \x ->
            (S.fromList [-3 .. 3 :: Int]) `rbind` \y ->
            rreturn $ x * y

do構文が使いたいですね。しかしdo構文はGHC.Base.Monadインスタンスでないと発動されません。残念。

Restricted Functor, Restricted Monad


この定義はすっきりしており自然な拡張ぽいので悪くないと思うのですが、そもそもGHCプラグマ依存ですし、GHC.Base.Monadがこんな感じに拡張されることは無いような気がします。
do構文の使用が緩和される方があり得そうですかね。

元論文について


上記コードはoriginal paperの定義とは少し異なりますしはそちらはあまり読めてませんごめんなさい。
他にもpaperにはUArrayをRFunctorのインスタンスにするといったことやComonadについても書かれています。圏論に関する部分は途中まで読んですっ飛ばしました。
型クラスの型制約に関しては圏論的に解釈するとHask圏のSubCategoryに相当するという記述や、止まらないプログラムとか意図的なものじゃないからと言って⊥が自然に無視されたことが印象的でした。あ、はい残りも読みます。