Arrowのことその3 - 取り急ぎブログです

前回までArrowの概要をザーッと流したわけなんですが、取りこぼしたことをいくつか…

ArrowはWrappedArrow経由でApplicativeとFunctorのインスタンスになっているようです。まぁ、関数(->)自身がApplicativeやFunctorのインスタンスなので、関数をくるんだArrowがそうであるのもわからないではないですね…

Arrowのクラスインスタンスには関数(->)のほかに：

Monad m => Arrow (Kleisli m)

newtype Kleisli m a b = Kleisli { 
runKleisli :: (a -> m b)
}

というのがあって、モナドのバインド(>>=)の第2引数にあたるシグネチャの関数をArrowとして扱うことができるようになっています。普通のdo文では最初の行以外は全て基本的には>>=てつながっているので、つまり、do文は型的には：

m a >>= a -> m b >>= b -> m c….

となっているので、それと同じようなことを>>>使って書くことができそうです。

(runKleisli (Kleisli (a -> mb) >>> Kleisli (b -> mc) ) ) m a

なんてことになるんでしょうか…

さらに、Kleisli mはArrowChoiceのインスタンスにもなっているので、分岐などの表現もArrow的に行うことができるようです。

さて、Generalizing Monads to Arrowsの論文でも取り上げられていたことなのですが、なぜパーサーはMonadではうまくかけなかったのでしょう？

論文による説明では、ArrowがMonadよりもうまくパーサのデザインに適応できる理由は間接的なものです。概略はこんな感じです：
簡単にMaybeを使ったモナド的なパーサのシグネチャを見てみるとこんな感じです：

Parser s a = P([s] -> Maybe (a, [s]) )

ここで[s]は入力ストリームを、aはパースの結果のトークンを表しています。つまり、Parserは入力ストリームから何かとって、それをトークン化したものと、入力ストリームの残りのをタプルに入れて返す関数ということですね...でも、入力がマッチしなかった場合はNothingを返す…

そして、並列的にこのパーサ要素をMonadPlusの`mplus`演算子で連結しながら列挙すると最初にJustな値を返すパーサ要素が適用されるわけなんですが、こんなようなパーサ構成要素をくみ上げていって複雑なパーサを形成すると、いろんなところで、Nothingが帰ってくる可能性が出てきて、ひどいときにはたくさん入力を読み込んで、散々パースが成功し続けた挙句に、最後の一文字でNothingになってしまい、結果的にパースの一番最初の時点からマッチのやり直しが起きたりするわけです。そうゆう動きをするコードをHaskellで書くと、ガーベージコレクションできるデータの量が極端に少なくなって｢スペースリーク｣というものを起こすんだそうです。

立ち返って、パーサを書いてパースしたい文法というのは一般的にそんなに深いバックトラックが必要なものはあまりないらしくて、ある程度のレベルのバックトラックは重要なんだけれども、いつまでたってもなくならないバックトラックの可能性というのはどうやらパーサの実用度という面ではあまり高くなく、むしろメモリにプレッシャーがかかるだけという代物のようです。

そこで、考案されたのが、パーサ一つ一つがパースできる文字列の最初の1文字をデータとして持つというモデルです。そうすることで、複数のパーサ要素が並列に存在する場合、コンビネーター側でマッチする可能性があるパーサ要素をある程度限定することができるということらしいです。そしてついでに深いバックトラックの可能性を減らすことができます。

しかしながら、このことはコンビネータにパーサ要素が両方とも（コンビネータは2項演算子だということにして...）見えてくれなくてはいけないわけです。
これはつまり(>>=):: m a -> (a -> m b) -> m bであるモナドのバインドでは~~役不足~~2項目のパーサ要素が１文字目に何をとるかがわかっても、第一項のもなどのほうがわからない…

そこでモナドの返す値を次の関数に渡す形の>>=ではなく、>>>:: a b c -> a c d -> a b dなArrowが出てきたということらしいです。
つまり、ArrowはMonadよりも効率がいいとかそうゆうことではなく、パースを効率よくするためのパーサのデザイン変更がMonadのサポート外だったということのようです。

以上、Arrowのお勉強でした。
ではでは。