ARROWS - ラシウラ

ACM Digital LibraryでProceedingsの大部分のPDFが無登録でも取り出せるようになっていたみたいなのでそのテスト。

403 - Forbidden Access to The Digital Library

ただ、PDFの直リンクを取り出すときに、firefoxではPDFを開かないといけないのはつらいものがある。

で、「A New Notation for Arrows」というICFP01の論文:

http://delivery.acm.org/10.1145/510000/507664/p229-paterson.pdf?key1=507664&key2=7328852511&coll=ACM&dl=ACM&CFID=15151515&CFTOKEN=6184618

結局、Monadとの違いは、Monadがoutputだけを受け渡しで使える(o <- monad)のに対し、Arrowはinputも使える(o <- arrow -< i)というところなのだろうか。これによってループ表記が書けるようになるのだろう。

論文を読む前に、Arrowの仕組みを体感したほうがいいかもしれない。

HaskellのArrowsページ

http://www.haskell.org/arrows/

procシンタックス

http://www.haskell.org/arrows/syntax.html

Control.Arrowモジュール

http://web.mit.edu/ghc/www/libraries/base/Control.Arrow.html

Arrow構文例

import Control.Arrow

addA :: Arrow a => a b Int -> a b Int -> a b Int
addA f g 
  = proc x -> 
     do y <- f -< x
        z <- g -< x
        returnA -< y + z

この例の図

図を見ればaddAが何をするのかは一目瞭然ではある。addA f gは、多相型bなxを受け取って、それをそれぞれfとgに食わせた結果の値を足しあわせて返すコマンドになっている。ghciでは子のコードのようなproc構文を使うには-farrowsオプションをつける必要がある。

また、これはそのまま、addA succ succ 10のように使える関数になる。厳密にはaddA (arr succ) (arr succ) 10ではあるが、instance Arrow (->)となっている(当然ながら、その arrは arr f = f)。つまりそのため(addA succ succ)は関数として使える。逆に言えば、Arrowというのは、Parserのような関数的なモナドのための仕組みということもできるだろう。

これをArrowの基本メンバー(arr,>>>,first)だけで書いたのが、

import Control.Arrow

addA f g 
  = arr (\ x -> (x, x)) >>>
    first f >>> 
    arr (\ (y, x) -> (x, y)) >>>
    first g >>> 
    arr (\ (z, y) -> y + z))

とのこと。こちらは-farrowsオプションはいらない。

上図を|||で4つにスライスしてみると、(入れ替えを抜かせば)こういう感じになるように見えてくる。

arrは関数をArrowにする（Monadのreturnに似てるかも）。最初のarrの関数は二つにコピーしている。
first fというのは入力は二値のタプルで、一番めをfに食わせた結果、二番めはそのままをタプルにしたものを出力にする(1番目だけにfを適用)。
入れ替えてるのは、分岐を続きのように使うため
最後は足したひとつのintを返すArrowを作る

addA3を考えてみよう

addA f g h
  = arr (\ i -> (i, i)) >>>
    first f >>> 
    arr (\ (of, i) -> (i, (i, of))) >>>
    first g >>> 
    arr (\ (og, (i, of)) -> (i, (of, og))) >>>
    first h >>> 
    arr (\ (oh, (of, og)) -> of + og + oh))

なんとなーくわかった気がする。

JavaScriptで実装できるかなあ。とりあえず、ふつうのParserArrowでも書いてみるか。