Applicative よりも Monad の方が力が強い理由

Applicative よりも Monad の方が力が強い理由を考えるためのメモ。これから議論するためのたたき台なので、そう思って読んで欲しい。

コンテナで包む return

Monad とは、コンテナである。コンテナは、文脈を表す。たとえば、Maybe というコンテナは、失敗するかもしれない計算という文脈を表す。

通常の値や関数を文脈に入れるための API が return である。

return :: a -> ma

コンテナ内での関数適用 <*>

以下のような型を持つ関数を考える。

f :: a -> b

この関数を return を使って文脈の中に入れてやると、型は次のようになる。

return f :: m (a -> b)

この関数を、コンテナ内にある値に適応するための API が (<*>) である。

(<*>) :: m (a -> b) -> m a -> m b

コンテナへ持ち上げる <$>

fmap は、Functor の API であり、その別名を (<$>) という。型は以下の通り。

(<$>) :: (a -> b) -> m a -> m b

(<$>) を上記の関数 f に適用してみると、関数が文脈に持ち上げられることがはっきりする。

(f <$>) :: m a -> m b

<$> と <*>

(<$>) は、関数 f を return で文脈の中に入れ、(<*>) を用いて文脈の中の引数に適用することと同じである。

(<$>) :: (a -> b) -> m a -> m b
f <$> m = pure f <*> m

型クラス構成の順番がしっくりこないが、

(<$>) という API を定義しているのが Functor
加えて、return (本当は pure) と (<*>) という API を定義しているのが Applicative

である。

Applicative スタイル

文脈の中にある関数は、文脈の中にあっても、普通の Haskell の関数と同じ性質を持つ。つまり、カリー化されている。ここでは、関数が複数の引数を取ると俗っぽく表現していいことにしよう。関数に適応した引数の個数が、全体の引数の個数より小さければ、部分適応された関数が、文脈の中にあることになる。

よって、<*> を複数使って、次々と文脈の中の値に適用していける。一般的な形はこうなる。

f <$> m1 <*> m2 <*> ... <*> mn

上記の議論から (<*>) だけでも表現できるのは明らかだが、冗長なので好まれない。

return f <*> m1 <*> m2 <*> ... <*> mn

Functor と Applicative の限界

コンテナをプログラムの部品だと考えよう。(たとえば、パーサーなど。) これらをくっつけて、大きなコンテナを作りたくなる。(小さなパーサーをくっつけて、大きなパーサーを作る。)

(<*>) でくっつけられるコンテナの数は、いくつだろうか？もちろん、関数 f の引数の個数だけである。

では、(<$>) ならどうか？以下のように、関数を持ち上げていくつでも適用できるが、コンテナの大きさは、元のままである。((<$>) は左結合であることに注意。)

h <$> g <$> f <$> m

Functor 則を使って変換すれば、そのことがはっきりする。

(h . g . f) <$> m

Monad の登場

コンテナ同士をくっつけて、任意の大きさのコンテナを作るには、return、(<*>)、(<$>) では不十分だと分かった。そこで、Applicative にさらなる API を加えて強力にした型クラスが必要である。

それが Monad であり、新しい API が (>>=) である。(>>=) の型は以下の通り。

(>>=) :: ma -> (a -> mb) -> mb

(<*>) では、第一引数のコンテナの中身が関数である必要があった。これは強い制約であり、そのために任意の個数くっつけられないと言える。一方 (>>=) は、第一引数のコンテナの中身が値でもよい。

(<*>) では、左右のコンテナは、なんの関連も持てない。しかし、(>>=) では、左のコンテナの中にある値に応じて、右で作られるコンテナの中身が変化できる。

例

よくあるデータ構造として「型・値」を取り上げる。たとえば、「型」は1バイトで表現されており、「値」は3バイトの固定長であると考えよう。このパーサーは、Applicative で書ける。なぜなら、前のパーサーの結果に、後のパーサーが依存しないからである。

data TV = TV Type Value

tvParser = TV <$> typeParser <*> valueParser

次に、こちらもおなじみのデータ構造「型・長さ・値」を考えよう。「長さ」は「値」のバイト数を表す。「値」のパーサーは、「長さ」のパーサーの結果に依存するので、Applicative では表現できず、Monad の登場となる。

data TLV = TLV Type Value

tlvParser = do
    typ <- typeParser
    len <- lenParser
    val <- valueParser len -- 前の結果を使う
    return $ TLV typ len val

あどけない話

Internet technologies