読者です 読者をやめる 読者になる 読者になる

めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

Functor/Applicative Functor/Monadの関係を整理してみる

何の話かというと

ほぼ独り言のエントリですが。。。。

昨日、某所の「すごい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

とする時、次の2つは同じ意味になります。

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)よりも一般性の高いものと考えられそうですね。