SetはFunctorである
Haskell Advent Calendar 2013 9日目です。
概要
SetはFunctor。
なぜ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
Restricted Functor, Restricted Monad
この定義はすっきりしており自然な拡張ぽいので悪くないと思うのですが、そもそもGHCプラグマ依存ですし、GHC.Base.Monadがこんな感じに拡張されることは無いような気がします。
do構文の使用が緩和される方があり得そうですかね。