副作用のあるArrowの自作 1
副作用のあるArrowを自作してみます。id:MaD:20070816#1187319817で作ったやつは実用性がないので、新しい題材としてストリームに対してのシーケンシャルアクセスを記述するためのArrowを作ってみます。
簡単の為、これから作るArrowの基本動作は以下の2つだけとします。
- インプットストリームから1文字読む
- 読んだ値を使って計算を行う
Arrowの名前はSequential ProcessorからSPとします。
同じ名前のArrowがStream processingを実現するものとしてすでにありますが、これとはまったく別の単純なものです。
Arrowの構造を決める
まずArrowを作る際にはどういう構造にするかをよく考えて決める必要があります。
どのArrowにも必ず入出力のラインが１つずつあります。ここで注意したいのは、「inputとoutputは相異なる多相型でなければならない」ということです。
「必ず入力はInt」とか「必ず入力と出力が同じ型」などといったことは出来ません。*1ストリームの型は固定ですから、input, outputとは別にストリーム用のラインを用意します。
SPの場合は下図ようなイメージで作ります。通常時にはinput -> outputのラインを計算の為に使用し、ストリームを読みたい場合にはstrem -> outputとバイパスさせます。
この計算をそのまま表現する関数の型は
type SPF c i o = (i, [c]) -> (o, [c])
となります。ストリームはとりあえずc型のリストとして表しました。純粋関数型言語ではこのように、副作用を処理対象(ストリーム)を引数、戻り値として受け渡す事で表現します。
SPF型の関数をいちいち書いていくのは面倒なので、処理を簡単に書けるようにArrowを用意します。そして、最後にArrowからSPF型の関数を合成して実行できるようにします。
SP型の定義
SPにできることは「入力から１文字読む」と「通常の計算を行う」ことだったので以下の3つを用意します。*2
data SP c i o where Read :: SP c i c Pure :: (i -> o) -> SP c i o SP :: SPF c i o -> SP c i o
- Read : 入力から1文字よみ、outputに出力（だからoutputの型がc)
- Pure : input, outputに対する通常の計算。i -> o型の関数を内部に持つ
- SP : ReadやPure等を合成した結果を表現する。SPFを内部に持つ。
次にrunSPを定義します。run関数はArrowから実際の計算を合成するという事をします。
runSP :: SP c i o -> SPF c i o runSP Read (_, c:cs) = (c, cs) runSP Read (_, []) = (undefined, []) runSP (Pure f) (i, cs) = (f i, cs) runSP (SP f) state = f state
Readはinputを読み捨て、ストリームの先頭文字を出力します。ストリームが空の場合は未定義値を返します。*3
入力を読み捨てないで、inputと読んだ文字をタプルにして返すみたいな定義もできますが、ここはできるだけシンプルにした方が通常の関数に繋げやすくなります。Arrowにはinputを保存する為の仕組みとしてfirstがあるので、これでいいんです。
Pureはストリームに対して何もしません。Pureは後にpure,arrの定義として使いますが、id:MaD:20070816#1187319817で書いたArrow則を満たす為には、絶対にPureは副作用を起こしてはいけません。コンパイル時にArrow則に基づいてpureの付け替えなどの最適化が行われますので、副作用があると期待通りに動きません。
ここまでの実行例。
> :load "SP.hs" [1 of 1] Compiling SP ( SP.hs, interpreted ) Ok, modules loaded: SP. > runSP Read ((), [1, 2, 3]) (1,[2,3]) > runSP Read ((), []) (*** Exception: Prelude.undefined > runSP (Pure (+ 1)) (1, [1, 2, 3]) (2,[1,2,3])
SPの合成の定義
SP cをArrowのインスタンスにします。
instance Arrow (SP c) where pure = Pure first = spFirst (>>>) = spSeq spFirst :: SP c i o -> SP c (i, a) (o, a) spFirst sp = SP $ \((i, a), cs) -> let (o, cs') = runSP sp (i, cs) in ((o, a), cs') spSeq :: SP c i a -> SP c a o -> SP c i o spSeq sp1 sp2 = SP (runSP sp1 >>> runSP sp2)
spFirstは入力された(i, a)のうち、iだけをspに渡しaはそのままにして出力します。これで入力を保存する仕組みが実現できます。この定義はArrow則を満たしているはずですが、証明は自分でもしていません。
spSeqはそれぞれrunして関数にしてから合成するだけです。
SPの動作
このReadとPureだけでいろいろ遊べます。
1文字読んで計算
例えば、1文字読んで、それに対して計算を行う処理は
> runSP (Read >>> pure(+1) >>> pure show) ((), [1, 2, 3, 4, 5])
("2",[2,3,4,5])
> runSP (Read >>^ (+1) >>> show) ((), [1, 2, 3, 4, 5])
("2",[2,3,4,5])みたいに書けます。>>^はそこより右側を通常の関数合成に切り替える演算子です。他に^>>とか^<<とか<<^とかありますが、すべて挙動が違います。定義は下の様にarrを付けているだけですが、これらは全て右結合性なので注意してください。
f ^>> a = arr f >>> a a >>^ f = a >>> arr f a <<^ f = a <<< arr f f ^<< a = arr f <<< a
^>>や^<<は1つだけにarrをつけたい場合に使います。
> runSP (Read >>> (+1) ^>> pure show) ((), [1, 2, 3, 4, 5])
("2",[2,3,4,5])>>^や<<^は右側全てにarrをつけます。
n文字目だけ読む
Readは入力を読み捨てますので、例えば3文字目まで読み進めたかったら
> runSP (Read >>> Read >>> Read) ((), [1, 2, 3, 4, 5]) (3,[4,5])
とします。こういうよく使いそうな関数は
seek :: Int -> SP c i c seek n | n <= 0 = undefined | n == 1 = Read | n > 1 = seek (n-1) >>> Read
みたいな関数にしとくと便利ですね。
> runSP (seek 5) ((), [1, 2, 3, 4, 5, 6, 7]) (5,[6,7])
本当はundefinedを使わずエラー処理をすべきなんですが、簡単の為こうしてます。
入力の保存
入力を2つに複製し、firstを使うと入力を保存することができます。
> runSP ((\x -> (x, x)) ^>> first Read) (0, [1, 2, 3, 4, 5]) ((1,0),[2,3,4,5])
&&&演算子を使うと複製、first,secondの適用を一辺にやってくれます。上の代わりに
> runSP (Read &&& pure id) (0, [1, 2, 3, 4, 5]) ((1,0),[2,3,4,5])
と書けます。
例えばよく使いそうな、入力を1文字スキップするSPは
skip :: SP c i i skip = Read &&& pure id >>^ snd
と書けます。
&&&演算子の挙動
この&&&演算子がものすごく面白い動作をします。
例えば、&&&でReadを繋げると
> runSP (Read &&& Read &&& Read) ((), [1, 2, 3, 4, 5]) ((1,(2,3)),[4,5])
となります。&&&演算子は演算を並列化するものと捉えられる事が多いですが、並列化するのは入力、出力のみで、副作用まで並列化するわけではありません。*4
標準ライブラリの&&&のデフォルト実装は
f &&& g = arr (\b -> (b,b)) >>> first f >>> second g
となっているのでまず&&&の左が実行され、次に右が実行されます。
この動作を利用すると入出力のラインをスタックとして使用することができます。例えば入力の1, 4, 6文字目だけを読みたかったら
> runSP (Read &&& (skip >>> skip >>> Read) &&& (skip >>> Read)) ((), [1, 2, 3, 4, 5, 6, 7, 8]) ((1,(4,6)),[7,8])
とします。&&&で囲まれた部分の計算結果がスタックに積まれるという風に読めます。
これとpureを組み合わせると
> runSP (Read &&& (skip >>> Read) >>^ uncurry (+)) ((), [1, 2, 3]) (4,[])
出力がリストでなくタプルになるメリットとして、異なる型の値を格納できるということがあげられます。
> runSP (Read &&& (Read >>^ show)) ((), [1, 2, 3, 4]) ((1,"2"),[3,4])
これはパーサのシフト&リデュース動作に似ているわけで、Arrowを使えばParsecみたいにわざわざdo記法を使わなくてもいいパーサが作れるな、って気づきました。今作ってるパーサライブラリではこういう書き方ができるようにしています。
n文字読む
以上を応用してn文字読むSPを作ってみます。
readN :: Int -> SP c i [c] readN n | n < 0 = undefined | n == 0 = pure (const []) | n > 0 = Read &&& readN (n-1) >>^ uncurry (:)
あらかじめフォーマットが決まった何かをパースするくらいには使えそうです。
> runSP (readN 3 &&& (skip >>> readN 4) &&& (skip >>> readN 4) >>^ (\(x, (y, z)) -> x ++ y ++ z)) ((), "090-1234-5678") ("09012345678","")
サンプル
runSPの呼び出しをラップする関数を用意しました。
runSeqProcessor :: SP c i o -> i -> [c] -> o runSeqProcessor sp input cs = fst $ runSP sp (input, cs)
まだ条件分岐が出来ないので入力に依存した処理はできません。
アイデアが出てこなかったので、5文字に1回失敗するcatプログラム...orzを作ってみました。
% cat catoid.hs import SP cat = (readN 4 >>> skip) &&& cat >>^ \(xs, ys) -> xs ++ ys main = getContents >>= (runSeqProcessor cat() >>> putStr)
% ghc --make catoid.hs [2 of 2] Compiling Main ( catoid.hs, catoid.o ) Linking catoid ... % ./catoid < catoid.hs impot SPcat (redN 4>>> kip)&&& at >^ \(s, y) ->xs + ys ain getontets >= (rnSeqrocesor at()>>> utSt) catoid: Prelude.undefined
最後はundefinedが返って終了しますので、やっぱり条件分岐を実現しないとまずいですね。
今後の改良
現状の機能ではわざわざArrowにする意味があまりないので、これから改良をしていこうと思います。
やってみたいと思っている事は
- ArrowChoice, ArrowZero, ArrowPlus, ArrowApply, ArrowLoopへの対応。
- 入出力が扱えるようにする。
- 今はSPFが関数ですが、Arrow化すればKleisli IOを使用できるようになります。標準入力を繋げれば、標準入力から1文字ずつ読んで、標準出力に何かを出力するようなプログラムがArrowで書けるようになります。
- リスト以外のストリームでも使えるようにする
- Read動作だけジェネリックに作れればいいので、Data.Traversable, Data.Foldable, Data.Sequenceあたりのどれかで実現できそう。
- 静的に計算方法を表現できるArrowならではの何か。最適化とか。
またSPをちょっと応用すれば
- アウトプットストリーム
- 双方向ストリーム
- ランダムアクセスストリーム
などが作れると思います。
最終的にはこれらを使ってストリームを処理するアプリケーションをすっきりと書けるようにすることが目標です。
