ArrowによるHaskellプログラミングの基礎。…パイプ感覚で順次/分岐/繰返し

Haskell

Programming with Arrowsを読んで理解したつもりのメモ。誤りなど乞うご指摘。

（復習）Arrowってなに？

と思って以前調べたメモが"3分で解るHaskellのArrowの基本メモ - よくわかりません"。それにちょっと補足というか観点を変えてまず感覚の整理。


Monadに色んな種類があるように、Arrowも色んな種類がある。

  • Monad: IO、Maybe、…
  • Arrow: 関数そのまんま(->)、Kleisli m、…


ある種類のMonadに色んな型の色んな値を入れられるように、ある種類のArrowに色んな型の色んな関数を入れられる。

  • Monad: Maybeの例→ 「Maybe Int」 にreturn 0ã‚‚return 777もＯＫ。「Maybe Char」 にreturn 'a'ã‚‚return ' 'もＯＫ。
  • Arrow: (->)の例→ 「Int -> Int」 にarr (+1) ã‚‚arr (*2)もＯＫ。「Char -> Char」 にarr toUpperã‚‚arr toLowerもＯＫ。

普通にパイプで繋ぐ … 順次処理構造

ふつうにArrowを「>>>」で繋ぐ。Arrowの種類が(->)つまり関数そのまんまの場合の例だと、

numOddOver10 :: (->) [Int] Int
numOddOver10 = (filter odd) >>> (filter (>10)) >>> length

のように３つのArrow（のインスタンスである(->)）

  • (filter odd) :: (->) [Int] [Int]
  • (filter (>10)) :: (->) [Int] [Int]
  • length :: (->) [Int] Int

を、>>>で繋いで全体で(->) [Int] IntなArrow（のインスタンスである(->)）を作れる。まさにUnixのシェルでコマンドをパイプ(|)で繋ぐ感覚。

使ってみるとこんな感じ。

Main> numOddOver10 [0,1,10,8,13]
1
Main>

結果を、他の処理のあとで使う … 変数の代替

Unixのシェルでコマンドをパイプ(|)で繋げてて困るのが、出力を次のコマンドじゃなくてもっと後のコマンドに渡したい場合。その場合、一時ファイルのような外部記憶に一度吐いてまた読むという事になるけど、Arrowでは流れを論理上並列*1にできる。

それに便利なのがArrowのクラスメソッド(&&&)。

(&&&) :: arrow a b -> arrow a b' -> arrow a (b,b')

wikibooksにある概念図をみるとどんなものか解りやすい。


使用例。先の例の改変で、ただの奇数は1ポイント、10より大きい奇数はさらに10ポイントとしてカウントする。

numOddOver10Weighted :: (->) [Int] Int
numOddOver10Weighted = filter odd >>> 
                       ((filter(>10)>>>length>>>(*10)) &&& length) >>>
                       uncurry (+)


filter oddの出力が二股に分かれて、一方は&&&の左(filter(>10)>>>length>>>(*10))を通り、一方は&&&の右(length)を通る。これらの出力がタプルにまとめられてまた１本になってuncurry (+)に流れる。
まさにパイプ感覚というか流してる感覚。

並列系クラスメソッドは、ほかにfirst、second、(***)がある。それぞれどんなもんかはwikibooksの図を見れば解る。
ただ、流れが複雑になったらdo記法のArrow用拡張版で素直に変数を使った方が解りやすいかも。


値によって処理を分ける … 条件分岐構造

Unixのシェルでの、コマンドのパイプ連結だとお手上げ*2。シェルスクリプトでif文の出番。

Arrowの場合も、Arrow一般だとお手上げだけど、ArrowChoiceというサブクラスの範囲では大丈夫。Arrowの枠内で条件分岐が出来る。(->)もKleisli mも、ArrowChoiceのインスタンスになってるから大丈夫。


ArrowChoiceのクラスメソッドがこれ。ふたつのArrowを渡して、条件によってそのどっちかだけを通すArrowを作ってくれる。

    (|||) :: arrow a c -> arrow b c -> arrow (Either a b) c

条件入力にはBoolの代わりにEitherを使う。イメージは上に書いた&&&に近い。Arrowふたつ( arrow a c と arrow b c )を取り、arrow (Either a b) cに合成する。合成されたArrowは、入力がLeft aなら arrow a cに流し、arrow b cは使われない。入力がRight bならその逆。

使用例。20より大きい要素がある場合は奇数である要素数、ない場合は10より大きい要素数をカウントする。

numOddOrOver10 :: (->) [Int] Int 
numOddOrOver10 =  hasOver20 >>> 
                  (filter(>10) ||| filter odd) >>>
                  length 
    where hasOver20 ns | any (>20) ns = Right ns 
                       | otherwise = Left ns

Rightの時は|||の右のArrowを通り、Leftの時は|||の左のArrowを通る。


ArrowChoiceのクラスメソッドは、ほかにleft、right、(+++)がある。それぞれどんなもんかはリファレンスとか参照。


一定条件の間は繰り返す … 繰り返し構造

forとかwhileです。もはやパイプでは有り得ませんが、Arrowでは最後に自分を持ってくればおk。

ra = ga>>>fa>>>ra

もちろんこれじゃ無限ループなので、

ra = ga>>>fa'>>>(ra|||arr id)

みたいに条件分岐と組み合わせる。


（追記:当初、ここにArrowApplyでループという記事を書きかけてたけど、自分のガセ妄想だったようです。すみません）

というわけで何でも出来る

上記の通り、変数の代替があって、順次処理構造、条件分岐構造、繰り返し構造が作れるので、どんなプログラムでも書けるはず。

　　　　　　　+
　　　　　+　　+　　　　　 ／￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　　　　 ∧＿∧　　　　＜　 わーい構造化定理の３構造だー！　３構造だー
　　 br（´∀｀　）ﾜｰｲ !　 |　 　　何でもできるぞー
　+ 　　ヽ 　　　つ　 　　 ＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　 　　(⌒_ノ
　　　 　　 し'ゝ　;;::⌒::

かくして、純粋関数型言語Haskellの上に手続きプログラミングが華麗に再発明！



注意。実際はちゃんとarrしてArrowに

ここまで書いた例は(->)以外のArrowでは使えないコード。(->)以外のArrowでも使えるコードにするには、下のように関数をarrしてArrowにしてやらないとだめ。

numOddOver10 :: Arrow arrow => arrow [Int] Int
numOddOver10 = arr (filter odd) >>> arr (filter (>10)) >>> arr length

numOddOver10Weighted :: Arrow arrow => arrow [Int] Int
numOddOver10Weighted = arr (filter odd) >>> ((arr (filter(>10))>>>arr length>>>arr (*10)) &&& arr length) >>> arr (uncurry (+))
--こっちでも
--numOddOver10Weighted' = arr (filter odd) >>> (arr ((10*).length.(filter(>10))) &&& arr length) >>> arr (uncurry (+))
--numOddOver10Weighted'' = arr (filter odd) >>> (arr ((filter(>10))>>>length>>>(*10)) &&& arr length) >>> arr (uncurry (+))

numOddOrOver10 :: ArrowChoice arrow => arrow [Int] Int 
numOddOrOver10 =  arr hasOver20 >>> (arr (filter(>10)) ||| arr (filter odd)) >>> arr length 
    where hasOver20 ns | any (>20) ns = Right ns 
                       | otherwise = Left ns


断りなくあとで書き直すかも…。

追記:普通のArrowでは繰り返し構造が出来ないみたいに書いてたのを修正。

*1:実行が同時というわけではない

*2:もちろんコマンド自体が条件によって処理を変えるのは可能。それはArrowでもArrowの中の関数が条件によって処理を変えるのと同じ。ここではArrowのレベルでの条件分岐のルール（ツール）の話