YonedaとCoYoneda、そしてFunctor
本当は、
Freeモナドを超えた！？operationalモナドを使ってみよう
http://fumieval.hatenablog.com/entry/2013/05/09/223604
に影響されて、Operationalモナドの話をまとめようと思ったのですが、ちょっと時間なさそうだったので、今日はちょっとCoYonedaの話をしましょう。
上記ブログでは、CoYonedaについて「ただのデータ型からFunctorを生み出せる」と紹介されています、これがいったいどういう事か、ちょっと深く追ってみましょう。
初めに
今回は、任意の型をFunctorにする事が目標なので、まず簡単に以下のような型を定義しておきます。
data Hoge a = Foo a | Bar a deriving Show
米田先生とYoneda
Yonedaというのは米田信夫という日本の数学者の名に因んだ「米田の補題」と関係のある型・・・なんだと思います。
「思います。」というのは、単にブログ主が米田の補題を理解してない*1だけの話なのですが・・・
さて、ekmett氏によるcategory-extrasというモジュールの、Control.Functor.Yonedaモジュールに、Yonedaというデータ型が以下のように定義されています。
{-# LANGUAGE ExistentialQuantification, RankNTypes #-} data Yoneda f x = Yoneda { runYoneda :: forall b. (x -> b) -> f b }
YonedaはFunctorです。では、Yonedaをmapするというのはどういう事でしょうか。
これは、runYonedaの型がどう移り変わるか考えると、「「始域の関数」の始域」を書きかえる事になるのがわかります。
m :: Yoneda f x k :: x -> y とした時 m :: Yoneda f x fmap k m :: Yoneda f y ^ つまり runYoneda m :: (x -> b) -> f b runYoneda $ fmap k m :: (y -> b) -> f b ^
そのため、Yoneda型のfmapは次のように定義されています。
instance Functor (Yoneda f) where fmap f m = Yoneda $ \k -> runYoneda m (k . f)
以下のようにすると、実際に「「始域の関数」の始域」がfmapする度に変わっていく様子がわかります。
runYoneda $ Yoneda (\k -> Foo (k 5)) :: Num x => (x -> b) -> Hoge b runYoneda . fmap show $ Yoneda (\k -> Foo (k 5)) :: (String -> b) -> Hoge b runYoneda . fmap read . fmap show $ Yoneda (\k -> Foo (k 5)) :: Read x => (x -> b) -> Hoge b runYoneda . fmap (*2). fmap read . fmap show $ Yoneda (\k -> Foo (k 5)) :: (Num x, Read x) => (x -> b) -> Hoge b
Yonedaの双対CoYoneda
さて、今度はYonedaの双対を考えてみます。
基本的には関数の矢印の向きを逆にすれば良いので、runYonedaに対応するrunCoYonedaは次のように考えれば良いですね。
| runYoneda | runCoYoneda |
|---|---|
| (x -> b) -> f b | f b -> (b -> x) |
これを元に、CoYoneda型と、そのFunctorを定義すると次のような感じになります。
data CoYoneda f x = CoYoneda { runCoYoneda :: forall b. f b -> (b -> x) } instance Functor (CoYoneda f) where fmap f (CoYoneda g) = CoYoneda $ \x d -> f $ g x d
CoYonedaのfmapは、「「終域の関数」の終域」を書きかえる事になります。
m :: CoYoneda f x k :: x -> y とした時 m :: CoYoneda f x fmap k m :: CoYoneda f y ^ つまり runCoYoneda m :: f b -> (b -> x) runCoYoneda $ fmap k m :: f b -> (b -> y) ^
えー、実際に書いてみるとよく解ると思うんですが、このCoYonedaの定義はｽｯｹﾞｰ使いづらいです。
このまんまだとちょっと使い物にはならなさそうなので、形を変えてみましょう。
f b -> (b -> x)という型は、次のように考える事ができます。
(->) (f b) (b -> x)
この、(->)をデータコンストラクタCoYonedaに置き換えてみましょう。
CoYoneda (f b) (b -> x)
つまり、CoYonedaとは、f bという値と、(b -> x)という関数のペアと考える事ができます。*2 *3
ここで、fmapによって(b -> x)の終域を書きかえるのは簡単です。(x -> y)という関数と関数合成すれば(b -> y)という型を得ることができます。
従って、CoYonedaの型と、Functorの定義は次のようになります。
data CoYoneda f x = forall b. CoYoneda (f b) (b -> x) instance Functor (CoYoneda f) where fmap f (CoYoneda v g) = CoYoneda v (f . g)
こうすれば、任意の型をCoYoneda型に持ち上げるliftCoYonedaの定義は簡単です。
liftCoYoneda :: f a -> CoYoneda f a liftCoYoneda x = CoYoneda x id
元の定義から(f b)と(b -> x)を入れ替えると、liftCoYonedaの定義はもっと簡単になります。
{-# LANGUAGE ExistentialQuantification #-} data CoYoneda f x = forall b. CoYoneda (b -> x) (f b) instance Functor (CoYoneda f) where fmap f (CoYoneda g v) = CoYoneda (f . g) v liftCoYoneda :: f a -> CoYoneda f a liftCoYoneda = CoYoneda id
というかこれなら、liftCoYonedaの定義は不要なくらいですね・・・実際にこのCoYonedaはcategory-extrasに定義されているものと同じです。
この改訂版CoYoneda型はなかなか優秀です。まず値を作るのが簡単なのが良いですね。
CoYoneda id (Foo 5) :: Num x => CoYoneda Hoge x CoYoneda id (Bar "Hoge") :: CoYoneda Hoge [Char]
CoYonedaはFunctorなので、当然fmapできます。
let foo5 = CoYoneda id (Foo 5) :: CoYoneda Hoge Integer として fmap show foo5 :: CoYoneda Hoge String
さて、ここからが問題です。
CoYoneda Hoge aから、Hoge aだけ取り出すにはどうすれば良いでしょうか？
えー・・・
結局ですね、パターンマッチしてデータコンストラクタの数だけCoYonedaを剥がす計算を書いてやる必要があるんですね・・・
runFoo :: CoYoneda Hoge a -> Hoge a runFoo (CoYoneda f (Foo a)) = Foo (f a) runFoo (CoYoneda f (Bar a)) = Bar (f a)
なんやー(´・ω・`)これなら普通にHogeをFunctorにしたほうがえーやんなー・・・
と、思いません？
僕は思います。
もし、Freeモナドを知らなければね
Free+CoYoneda→Operational
Freeモナドについて詳しい事は、ブログ主の過去の記事とか、@fumievalさんの記事でも参照してください。
任意のFunctorをモナドにする事ができ、それによって簡単に言語内DSLが作れるすぐれものでしたね。
何も無い所からFunctorを作るのがCoYoneda、Functorからモナドを作るのがFreeモナド、では、この二つを組み合わせたらどーなるのっと。
type Program f a = Free (CoYoneda f) a data MyPg a = Order1 a | Order2 a type MyProgram a = Program MyPg a singleton :: f a -> Program f a singleton = liftF . liftCoYoneda order1 = singleton $ Order1 () :: MyProgram () order2 = singleton $ Order2 () :: MyProgram () runMyPg :: MyProgram a -> IO a runMyPg (Free (CoYoneda f o)) = runOrder o >>= runMyPg . f where runOrder :: MyPg a -> IO a runOrder (Order1 n) = putStrLn "Order1 Called!!" >> return n runOrder (Order2 n) = putStrLn "Order2 Called!!" >> return n runMyPg (Pure a) = return a ---- -- Test -- program :: MyProgram () program = do order1 order2 order2 order1 main :: IO () main = runMyPg program
実行結果：
Order1 Called!! Order2 Called!! Order2 Called!! Order1 Called!!
こうなります。
MyPgをFunctorにする事無く、Freeで言語内DSLに仕立て上げてしまいました。
「Freeよりも簡単にモナドが作れる！」が売り文句のOperationalはこんな仕組みらしいです。
ブログ主もいずれ、詳しい事書きますが、「勿体ぶってんじゃねぇよ！！」という方は、冒頭で紹介した@fumievalさんの記事をもう一度記載しますので、参照してください。
Freeモナドを超えた！？operationalモナドを使ってみよう：
http://fumieval.hatenablog.com/entry/2013/05/09/223604
おまけ
「ところでブログ主、category-extrasをインストールしていないらしいけど」
「・・・（黙秘）」
「またcabalの依存関係が解決できなかったんですか？」
「・・・（泣き顔）」
「ザコですね」
「・・・ｳｯ・・・ｳｯｳｯ・・・（号泣）」
