# HG changeset patch
# User Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
# Date 1391448418 -32400
# Node ID a7981a22f12e2456f463c7ffbbd560caa270d0a2
# Parent  8d934599d0c56c977b8444ed97e465c536b06c98
describe the eval monad

diff -r 8d934599d0c5 -r a7981a22f12e paper/chapter1.tex
--- a/paper/chapter1.tex	Tue Feb 04 01:32:16 2014 +0900
+++ b/paper/chapter1.tex	Tue Feb 04 02:26:58 2014 +0900
@@ -276,68 +276,85 @@
 
 当然これだけでは並列に動かず、並列に実行できるようにプログラムを書く必要がある。
 
-Haskell は遅延評価を行うため、必要となるまで式の評価が遅延される。
-普段は気にする必要はないが、並列実行ではどのように評価されるか意識する必要がある。
-並列に動くように処理を分割したとしても、値が必要になるまで評価されない。
-この問題は、Control.DeepSeq モジュールにある deepseq 関数を使用し、式を即時評価することで解決できる。
+Control.Parallel.Strategies モジュールにある、
+Eval モナドを用いた並列化について説明する。
+Eval モナドは並列処理を行うためのモナドである。
+
+Eval モナドで並列処理を行う使用例を示す。
+
+%% 完全に動くプログラム
+\begin{lstlisting}[caption=Evalモナドの使用例]
+import Control.Parallel.Strategies
+
+main = print (runEval test) 
+
+num :: Integer
+num = 1000000
 
-Haskellの並列化手法はいくつかあるが、その中で最もシンプルなのは Eval モナドを利用することである。
-Control.Parallel.Strategies モジュールをインポートすることで使用できる。
+test :: Eval (Integer, Integer)
+test = do
+    a <- rpar (sum' 0 num)
+    b <- rpar (sum' num (num*2))
+    return (a,b)
+
 
+sum' :: Integer -> Integer -> Integer
+sum' begin end = if begin < end
+                   then begin + (sum' (begin + 1) end)
+                   else begin
+\end{lstlisting}
+
+まず、Eval モナドが定義された、Control.Parallel.Strategies をロードし、Eval モナドを利用できるようにしている。
+
+Haskell のプログラムはmainという名前と実行したい関数を関連付けることで実行される。
+今回は、print (runEval test)が実行される。
 
 \begin{lstlisting}[label=eval, caption=Eval モナド]
 data Eval a
 instance Monad Eval
 
 runEval :: Eval a -> a
+rpar :: a -> Eval a
+\end{lstlisting}
 
-rpar :: a -> Eval a
-rseq :: a -> Eval a
+並列処理を行うには、rpar を使う。
+rpar で挟んだ関数は並列に実行される。
+Eval モナドの関数の型をみると、rpar は、a を モナドに包み、逆にrunEval はモナドから a を取り出している。
+rpar で並列化可能計算を示したあと、runEvalで実行する。
+
+test の = のすぐ後にあるdoはモナドのためのシンタックスシュガーであり、do 構文と呼ばれる。
+Haskell では、モナドを単一のモナドとするために、do構文を使う。
+$>>$= (bind)を使ってまとめることもできるが、do 構文を使うことでbindの入れ子構造を手続き言語のような書き方で書くことができる。
+do 構文を用いない場合、以下の様な式になる。
+
+\begin{lstlisting}[caption=do構文を使わない場合]
+test :: Eval (Integer, Integer)
+test = rpar (sum' 0 num) >>= (\a ->
+       rpar (sum' num (num*2)) >>= (\b ->
+       return (a,b)))
 \end{lstlisting}
 
-rpar は、引数が並列処理可能であることを示す。
-rseq は、引数を評価し、結果を待つように示す。
-どちらも式が完全に即時評価されるわけではないので、出力を挟んだり、deepseq 関数をうまく活用する必要がある。
-runEval は、評価を実行し結果を返す操作である。
-実際の利用方法として２つのパターンを紹介する。
-
+sum' は2つの引数をとって、開始点から終了点までの値をすべて足し合わせる関数である。
+並列処理に負荷を与えるために使う。
+ifで、開始点が終了点を超えてないか調べ、超えてなければ再帰的に呼び出して足し合わせを行う。
 
-\begin{lstlisting}[label=rpar/rpar, caption=rpar/rpar]
-runEval $ do
-   a <- rpar (f x)
-   b <- rpar (f y)
-   return (a,b)
-\end{lstlisting}
+test で返ってくる型は、Eval (Integer, Integer)で、その後 runEval 関数を適用することで、(Integer, Integer)となる。
+そして最後にprint で出力される。
+
+Haskell は遅延評価を行うため、必要となるまで式の評価が遅延される。
+今回の場合、最後のprintがなければそもそも計算が行われない。
 
-rpar/rpar パターンは即座に return される（図\ref{fig:rpar}）。
-単純に並列に動かしたい時に利用する。
+並列に動くように処理を分割した後は、Haskell の遅延評価に気をつける必要がある。
+値が必要となるprintなどを行えば、並列に実行可能な部分が並列に実行される。
+
+rpar を使用する際に気をつけるのは、別の計算の値に依存する計算がある場合、その2つの計算は並列実行できないということである。
+例えば、以下のような場合は並列実行ができない。
 
-\begin{figure}[!htbp]
- \begin{center}
-  \includegraphics[scale=0.6]{./images/rpar_rpar.pdf}
- \end{center}
- \caption{rpar/rpar パターン}
- \label{fig:rpar}
-\end{figure}
-
-\begin{lstlisting}[label=rpar/rseq/rseq, caption=rpar/rseq/rseq]
-runEval $ do
-    a <- rpar (f x)
-    b <- rseq (f y)
-    rseq a
+\begin{lstlisting}[caption=前の計算に依存した計算]
+test2 :: Eval (Integer, Integer)
+test2 = do
+    a <- rpar (sum' 0 num)
+    b <- rpar (sum' num (if a < num then a else (num*2)))
     return (a,b)
 \end{lstlisting}
 
-rpar/rseq/rseq パターンは、f x および f y の結果を待ってから return する（図\ref{fig:rseq}）。
-他の処理が結果を必要としている時に利用する。
-
-\begin{figure}[!htbp]
- \begin{center}
-  \includegraphics[scale=0.6]{./images/rpar_rseq.pdf}
- \end{center}
- \caption{rpar/rseq/rseq パターン}
- \label{fig:rseq}
-\end{figure}
-
-rparは非常にコストが低いため、リストに対してmapするといった適用の仕方でも充分な並列性が出る。
-そのための関数 parMap も、 Control.Parallel.Strategies モジュールには用意されている。
diff -r 8d934599d0c5 -r a7981a22f12e paper/master_paper.pdf
Binary file paper/master_paper.pdf has changed