Strategies（Parallel and Concurrent Programming in Haskell Chapter 3 前半）

以前まとめた第２章についてはこちら
http://jsapachehtml.hatenablog.com/entry/2015/01/03/101754
http://jsapachehtml.hatenablog.com/entry/2015/01/18/143520

英語の原文はこちらのページで読める
http://chimera.labs.oreilly.com/books/1230000000929/ch03.html

Strategyの導入

第２章で使ったEvalモナドを使いやすい形(Strategy)としてうまく使うというのが第３章
Strategyの型は以下

type Strategy a = a -> Eval a

任意のデータ型をとりEvalで包んで返す関数をStrategyと定義

具体的な使い方としてparPairを導入

parPair :: Strategy (a, b)
parPair (a, b) = do
  a' <- rpar a
  b' <- rpar b
  return (a', b')

a, bそれぞれを並列に計算した結果をtupleで返す

計算結果を取り出すにはrunEvalを適用すればよい
fib nはn番目のフィボナッチ数を返す処理

runEval (parPair (fib 35, fib 36))

さらに以下の関数usingを考えてみる

using :: a -> Strategy a -> a
x `using` s = runEval (s x)

xに計算したい値、sに評価の方法つまりStrategyを渡す

parPairは以下のように使える

(fib 35, fib 36) `using` parPair

こうすると何がよいのかというと
"何をするのか"と”どのようにするのか”が明確に分けられること

単純に計算した結果がほしいだけであればusing以降の部分は要らないし
実際にそれで計算できる

逆に言えば、行いたい処理を書いた上で後から`using` sの部分を付け足せば
並列化できるということ

Strategyのパラメータ化

上に書いたparPairはWHNFまでの評価を並列に行うことしかできない
別のことがやりたい場合、例えばNFまで評価するなどの場合、別の関数を新しく定義する必要がある
しかし、それでは無駄が多い
ではどうするかというと評価の方法まで引数として渡せるようにするというのが考えられる

evalPair :: Strategy a -> Strategy b -> > Strategy (a, b)
evalPair sa sb (a, b) = do
  a' <- sa a
  b' <- sb b
  return (a', b')

evalPairがなぜ3つ引数を取ってるのか？と思うかもしれないが（というか私は最初思った）
Strategyがa -> Eval aであることを思い出すと型通りになっていることがわかる

これを使って先ほどのparPairを定義し直すと以下のようになる

parPair = evalPair rpar rpar

ここでわかることはrpar（やrseq）はStrategyであるということ
考えてみるとたしかにrparはa -> Eval aの型になっている

もし、NFまで評価するようなparPairを作りたければどうするか？
上記の式でrparの代わりにNFまで評価を行うようなStrategyを渡せばよいはず
そのために以下を定義する

rdeepseq :: NFData a => Strategy a
rdeepseq x = rseq (force x)

これをevalPairに渡すと、NFまで評価するという処理をシーケンシャルに行うことになる
ここではこれを並列に処理したい
なのでもう一つ以下のような型の関数を定義

rparWith :: Strategy a -> Strategy a

渡されたStrategyをrparで包むというものである

これらによってNFまで評価するかWHNFまで評価するか引数で選べるparPairを定義できる

parPair :: Strategy a -> Strategy b -> Strategy (a, b)
parPair sa sb = evalPair (rparWith sa) (rparWith sb)

で、NFまで評価するparPairはこうなる

parPair rdeepseq rdeepseq :: (NFData a, NFData b) => Strategy (a, b)

リストを並列処理

第２章で出てきたparMapを、この章でやってきたように計算したい値とそれを並列化するという２つの部分に分ける
そうすると以下のように定義しなおせる

parMap :: (a -> b) -> [a] -> [b]
parMap f xs = map f xs `using` parList rseq

tupleに対して定義したのと同じようにリストについてもやってみる
つまり、Strategyをパラメータ化して引数に渡し、それによってリストの要素を処理する

evalList :: Strategy a -> Strategy [a]
evalList strat []     = reutrn []
evalList strat (x:xs) = do
  x' <- strat x
  xs' <- evalList strat xs
  return (x':xs')

リストの各要素に引数として渡したStrategyを再帰的に適用していくというもの

これを使ってparListを定義するとこうなる

parList :: Strategy a -> Strategy [a]
parList strat = evalList (rparWith strat)

この章で定義した関数はだいたいControl.Parallel.Strategiesというモジュールに含まれている
ここに書かれている以外のものもあるので見てみるといいかも
https://hackage.haskell.org/package/parallel-3.2.0.6/docs/Control-Parallel-Strategies.html

要点をまとめたというより細かい所を除いた和訳みたいになったが
Strategyの導入の意味や使い方は理解できた気がする

あと、このページの式については元のページから引用
http://chimera.labs.oreilly.com/books/1230000000929/ch03.html