Par Monad（Parallel and Concurrent Programming in Haskell Chapter 4)

第２章、第３章ではEvalモナドを使い
遅延評価と密接に結びついた状態で並列化を行った

このモデルだとアルゴリズムと並列化の処理を切り分けやすく
並列処理を組み立てやすいというメリットがある

ただ遅延評価を用いているデメリットとして
パフォーマンスを測定や改善がしづらいという点がある

第４章ではParモナドを導入しEvalモナドとは違う利点をもった並列化を考える
Parモナドでやりたいことは以下

具体的にどういうことを言っているのかここではわからないが
読み進めていくうちにわかるのだろうか？

こちらのモデルだと、プログラムする際に並列化の詳細を考えて書く必要が出てくる
（parListなどは処理とデータを渡せば並列処理は中でやってくれた）
しかし、その分細かな制御ができるという利点がある

Parから値を取り出すときはrunPar

runPar :: Par a -> a

目的である並列処理を行うための関数はfork

fork :: Par () -> Par ()

forkを呼んだ側の処理とforkに渡された処理が並列に実行されることになる

型を見るとforkは値を返さない
では並列化した処理の結果をどのように取得するのか？

そこで出てくるのがIVar

data IVar a

new :: Par (IVar a)
put :: NFData a => IVar a -> a -> Par ()
get :: IVar a -> Par a

IVarは箱のようなものとして捉えると考えやすい
newで箱を作る、putで箱に入れる、getで取り出す

putは既に値の入ったIVarに適用するとエラーとなる
getは空のIVarに適用すると中身が入るまで待つ

つまりIVarは一度中身が入ったら入れ替えることはできないimmutableなものである

注意点として、
２つのrunParがあったときに片方でIVarを生成して値を入れ、
それを他方のrunParに渡して使うということはできない
Parモナドは自身の中でIVarを生成し使用することを前提に作られているため
これを破ると実行時エラーやデッドロックが発生する可能性がある

ここでParモナドを使った簡単な処理の例

runPar $ do
  i <- new
  j <- new
  fork (put i (fib n))
  fork (put j (fib m))
  a <- get i 
  b <- get j
  return (a+b)

まず、空のIVarであるi, jを生成
forkを使うことでfibの計算をそれぞれ並列に行い、結果をi, jへ格納
i, jに値が格納されるとgetによって取り出されてa, bへ
最後に和をとって返す

ここでの並列処理を図で表すとこのようになる
f:id:y-kamiya:20150124141437p:plain
図は原文より引用

この図を見ると先ほどの処理が、データフローを形作っていることがわかりやすい
forkによって各頂点(node)が作られ、newによって辺(edge)が作られ、putやgetによって各頂点が関連づけられる

ここまでの話(とhackageにある例)で最初に書かれていたParモナドでやりたいことの内容がなんとなく理解できた

データの依存や粒度をよりわかりやすく表現
- forkによって処理する単位(node)を表現し、IVarによってnodeの関連(edge)を表現できる
遅延評価に依存しない
- 並列化した処理の実行はfork内の部分で行われる（putがNFDataを要求しているのはそのため）
- Evalモナドの場合、WHNFまでの評価なのかNFまでの評価なのかを気にしながらどこで処理が実行されるか考える必要があった
決定性を失わない
- プログラムが変わらなければrunParで得られる結果は毎回同じになる
- スケジュ―リングの都合で各nodeの実行順序が変わったとしても最終的に得られる結果は変化しない(IVarがimmutableであることが重要)

第２章で用いたparMapと同様のことをParモナドによって行うため
並列処理を行い結果を返すという機能を備えたspawnという関数を定義する
(この関数はControl.Monad.Parに定義されている)

spawn :: NFData a => Par a -> Par (IVar a)
spawn p = do
  i <- new
  fork $ do
    x <- p
    put i x
  return i

これを使ってparMapMを定義する

parMapM :: NFData b => (a -> Par b) -> [a] -> Par [b]
parMapM f xs = do
  xs' <- mapM (spawn . f) xs
  mapM get xs'

ここでの注目点は渡す関数fがParモナドを返すということ
つまりfの中でさらに並列処理を行うことも可能ということ

また、第２章で定義したものと違って
全ての計算を待ってから結果を返すようになっている
もし計算を待たずに返ってほしいのであればgetの処理をやめてIVarのリストを返すようにするとよい