何の話かというと
ほぼ独り言のエントリですが。。。。
昨日、某所の「すごいHaskell」輪読会に参加して、Applicative Functorの章を読みました。本の構成としては、Monadより先にApplicative Functorを定義して、その後の章で、Applicative Functorの拡張概念としてMonadを導入しており、「お。しぶぃねぇ」という感じでした。
なのですが・・・
Applicative Functorにおける<*>演算の具体例の一部で、Monadのdo記法を使用しており、その結果、「文脈から中身を取り出して演算できる（ような気分になれる）」というMonadの特徴と、「文脈から中身を取り出さなくても、文脈内で演算が完結できる」というApplicative Functorの特徴がないまぜになっている点がちと気になりました。
というわけで、私なりにApplicative FunctorとMonadの関係を整理しなおしてみました。
前提概念の整理
Fを型コンストラクタ（*->*）として、型aに対して、型Faを「型aに構造Fを付与したもの」と呼ぶことにします。（「すごいHaskell」本では文脈と呼んでいるやつですね。）
この時、一般に「構造を付与することはできても、構造を引き剥がすことはできない」という事に注意が必要です。
たとえば、「3 :: Int」にリスト構造を付与して、「[3] :: [Int]」とすることはできますが、「[3,4,5,6] :: [Int]」からリスト構造を引き剥がして、単一のInt値をとりだすことは不可能ですよね。
FunctorとApplicative Functorの特徴
「構造を付与した世界」の概念を使うと、FunctorとApplicative Functorの特徴は次のように説明できます。
1. Functorには、次の型を持つ演算が用意されています。
fmap :: (a->b) -> Fa -> Fb
つまり、「構造の無い世界の演算(a->b)」を「構造のある世界の演算に(Fa -> Fb)」に対応づける方法が用意されています。
2. Applicative Functorには、次の型を持つ演算が用意されています。
(<*>) :: F(a->b) -> Fa -> Fb
つまり、「構造を付与した演算F(a->b)」を「構造のある世界の演算(Fa -> Fb)」に対応づける方法が用意されています。<*>の具体的な定義は、Fの種類によってさまざまです。例えば、F=[]の場合は、次のようになります。
(<*>) :: [(a->b)] -> [a] -> [b] fs <*> xs = [ f x | f <- fs, x <- xs ]
前述のように「関数のリスト」から関数を取り出したり、「値のリスト」から値を取り出すことはできません。そこで、上の定義では、特定の関数/値を取り出すことをあきらめて、リストに含まれる全ての関数/値について、全部演算してしまえ、という戦略をとっている事が分かります。で、次のような計算が自然にできるわけですね。
Prelude> import Control.Applicative Prelude Control.Applicative> [(^2),(^3)] <*> [1,2,3] [1,4,9,1,8,27]
繰り返しますが、構造を引き剥がさずに、構造を持ったままで演算できることがApplicative Functorの特徴です。
Monadの特徴
上記の流れに乗ると、Monadは次のように特徴づけられます。
3. Monadには、次の型を持つ演算が用意されています。
flip (>>=) :: (a -> Fb) -> Fa -> Fb
つまり、「構造があるんだかないんだかよく分からない変な演算(a -> Fb)」を「構造のある世界の演算(Fa -> Fb)」に対応づける方法が用意されています。
(>>=)の特徴は、do記法を用いると際立ってきます。
ma :: Fa f' :: a -> Fb
とする時、次の２つは同じ意味になります。
mb = ma >>= f' mb = do a <- ma f' a
後者の「do記法」では、あたかも「ma」から構造を剥がしたものを「a」として、f'に代入しているように見えます。もちろん、do記法は、あくまで前者のSyntax Sugarであって、実際にそのような演算が行われているわけではありません。正しい理解としては、「a」という記号に「ma」を紐付けておいて、これをf'に代入すると、事前に「>>=」で定義されている演算が実行される、という事です。Monadの魔法は、「>>=」の定義にすべて詰め込まれているわけです。
ただまあ。。。。
そういう固いことを言わずに、素朴にdo記法を解釈すれば、あくまでdoブロックの内部に限定すれば、「構造を引き剥がす」というあり得ない操作ができてしまう、これがMonadの特徴ということになります。
MonadからApplicative Functorへ
前述の「doブロック内部では構造を剥がすことができる」というMonadの特徴を利用すると、Monadは、自然にApplicative Functorになる事ができます。つまり、Monadについては、<*>演算を自然に定義することが可能です。<*>演算は、「F(a->b)」と「Fa」から「Fb」を生み出す演算でした。
もしも！
「F(a->b)」と「Fa」から構造を引き剥がして、「a->b」と「a」を取り出すことができれば！
これをくっつけて、「b」を生み出すことができます。「b」にもう一回、構造Fをくっつければ、無事に「Fb」が出来上がります。Monadであれば、これをdo記法の内部で実現することが可能です。
mf <*> mx = do f <- mf x <- mx return (f x)
というわけで、Applicative Functorは必ずしもMonadではありませんが、Monadは必ずApplicative Functorにもなる事ができます。
ただし、上記の「中身を取り出して演算する」という形で<*>が定義されるのは、Monadの場合だけであって、一般のApplicative Functorについては、前述のように、「中身を取り出さずに、構造を持った世界の中で計算が完結できる」という事が重要なことに変わりはありません。
Monadの特徴に関する追記
冒頭のApplicative Functorの例でリスト[]を紹介しましたが、「リストもMonadだから、MonadではないApplicative Functorを特徴づける例としては不適当では？」という指摘をいただきました。確かに・・・・。リストの<*>演算も実際には、Monadとしての(>>=)演算から導出できてしまいます。
xs >>= f' = concatMap f' xs return x = [x]
という定義を使って、先の例を運算するとこんな感じになります。
[(^2),(^3)] <*> [1,2,3] = do f <- [(^2),(^3)] x <- [1,2,3] return (f x) = [(^2),(^3)] >>= ( \f -> [1,2,3] >>= ( \x -> [f x] ) ) = [(^2),(^3)] >>= ( \f -> concatMap ( \x -> [f x] ) [1,2,3] ) = [(^2),(^3)] >>= ( \f -> [ f 1, f 2, f 3 ] ) = concatMap ( \f -> [ f 1, f 2, f 3 ] ) [(^2), (^3)] = concat [ [1,4,9], [1,8,27] ] = [1,4,9,1,8,27]
ただ、この運算から分かるように、Monadの(>>=)演算も、do記法を使うと「リストから中身を取り出しているように見える」だけであって、実際に中身を取り出しているわけではありません。
[1,2,3] >>= ( \x -> [f x] ) = concatMap ( \x -> [f x] ) [1,2,3] = [f 1, f 2, f 3]
という評価から分かるように、実際には、「関数fをリストの中に突っ込む」という操作になります。つまり、Monadは、「構造から中身を取り出す」のではなく、「構造の中に外からプローブを差し込んで評価できる」というのが正しい理解かも知れません。Monadの場合は、「do記法を使って自然な感じで<*>が定義できる」というだけであって、Monadといえども本質的に「中身を取り出せる」わけではない、ということですね。
そういう目で、あえてdo記法をつかわずに<*>を(>>=)で書き下してみます。
fs <*> xs = fs >>= \f -> ( xs >>= ( \x -> return (f x) ) )
この場合は、「fs」と「xs」それぞれが構造を持っているので、次のように分解して理解できます。
(1) まずは、xsにプローブを差し込んでおく。（このプローブは、調整つまみ「f」を持っている）
probe1 f := xs >>= ( \x -> return (f x) )
(2) 続いて、fsにもプローブを差し込んでおく。
probe2 := fs >>= ( \f -> ... )
(3) (2)のプローブを(1)の調整つまみと結合して演算する。
probe2 := fs >>= ( \f -> (probe1 f) )
MonadではないApplicative Functorの例
それでは、そもそも、Monadから導出できないApplicative Functorはあるのでしょうか？ 例えば、次の<*>演算を持つZipListがあります。
追記：2013/10/16
以下の説明は嘘です orz。ZipListもMonadから構成することに成功した気がしてきました。こちらのエントリを参照下さい。。。。
ZipList [f,g,h] <*> ZipList [x,y,z] = ZipList [f x,g y,h z]
これは、Controll.Applicativeで次のように定義されています。
newtype ZipList a = ZipList [a] instance Functor ZipList where fmap f (ZipList xs) = ZipList (map f xs) instance Applicative ZipList where pure x = ZipList (repeat x) ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs)
ZipListで<*>演算を行う際は、fsとxsそれぞれの要素の位置（index）を合わせて評価する必要がありますが、一方、(1)のプローブの調整つまみ「f」は、「f :: a -> Fb」という型ですので、fsが持つ構造を意識する機能はありません。つまり、fsの要素fをxsの要素xに適用する際に、リストfsにおけるfの位置（index）のような情報は使えませんので、「Monadプローブ結合方式」で、ZipListの<*>演算を実現することはできません。
そういう意味では、やはり、Applicative Functorの「構造を保ったまま演算できる」という特徴は、Monad（から定義されるApplicative Functor）よりも一般性の高いものと考えられそうですね。
