--- a/paper/chapter1.tex	Tue Feb 11 19:45:40 2014 +0900
+++ b/paper/chapter1.tex	Tue Feb 11 22:58:43 2014 +0900
@@ -5,6 +5,7 @@
 関数とは, 一つの引数を取り一つの結果を返す変換器のことである. 
 関数型プログラミング言語では, 関数を引数に適用させていくことで計算を行う. 
 
+\subsubsection{関数の定義}
 既存の手続き型言語と異なり, 手順を記述するのではなく, この関数が何であるかということを記述する. 
 例えば, Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する. 
 Haskell は, 関数を引数を適用するという考えに基づいて, 抽象的なプログラミングを可能とする. 
@@ -19,22 +20,24 @@
 fib :: Int -$>$ Int は, 関数の型宣言である.
 この関数は, Int を受け取って Int を返す関数ということを示す. 
 フィボナッチ数列の関数が三行に渡って書かれているが, これは Haskell のパターンマッチを活用している. 
-引数が 0 ならば 2 行目の fib が呼び出される. 
-引数が 1 ならば 3 行目の fib が呼び出される. 
-上から順に引数と一致する行がないか調べていき, 引数が 0 でも 1 でもなければ引数は n に束縛される. 
+引数の値が 0 ならば 2 行目が呼び出され, 関数の結果は 0 となる.
+引数の値が 1 ならば 3 行目が呼び出され, 関数の結果は 1 となる.
+上から順に引数と一致する行がないか調べていき, 引数が 0 でも 1 でもなければ引数は n に束縛され, fib (n-2) + fib (n-1) が計算される.
 
 フィボナッチ数列の関数は, 自分自身を使って再帰的に定義している. 
 再帰は, 関数型プログラミング言語において必要不可欠な要素である. 
-手続き型言語では, 配列とループを主に用いてプログラミングを行うが, Haskell ではリスト構造と再帰を用いる. 
+手続き型言語では, 配列とループを主に用いてプログラミングを行うが Haskell ではリスト構造と再帰を用いる. 
 
+\subsubsection{変数の代入}
 純粋関数型プログラミングでは, 変数の代入は一度のみで後から書き換えることはできない. 
 フィボナッチ数列の関数でも, 一度引数を束縛した n を書き換えることはできない. 
 関数にできることは, 何かを計算してその結果を返すことだけであり, 引数が同じならば関数は必ず同じ値を返すことが保証されている. 
 この性質は関数の理解を容易にし, プログラムの証明を可能にする. 
 正しいと分かる単純な関数を組み合わせて, より複雑な正しい関数を組み立てていくのが関数型言語のプログラミングスタイルである. 
 
+\subsubsection{高階関数}
 関数型プログラミング言語は, 関数を変数の値にすることができる. 
-つまりこれは, 関数を第一級オブジェクトとして扱うことができるということである. 
+これは, 関数を第一級オブジェクトとして扱うことができるということである. 
 Haskell は, 引数として関数を取ったり返り値として関数を返すことができる高階関数を定義できる. 
 
 高階関数の例として Haskell のカリー化が挙げられる. 
@@ -43,6 +46,9 @@
 
 \begin{lstlisting}[label=src:max, caption=max関数]
 max :: Int -> Int -> Int
+max x y = if x <= y
+            then y
+            else x
 \end{lstlisting}
 
 この関数定義に現れる-$>$は左結合である. 
@@ -56,10 +62,11 @@
 カリー化によって, 関数を本来より少ない引数で呼び出した際に部分適用された関数を得ることができる（ソースコード\ref{src:partial}）.
 
 \begin{lstlisting}[label=src:partial, caption=関数の部分適用]
-x = max 3
-x 4 -- max 3 4 の結果として 4 が返される
+x = max 3 -- x は Int -> Int の関数
+x 4 -- (max 3) 4 の結果として 4 が返される
 \end{lstlisting}
 
+\clearpage
 \section{型}
 Haskell では, すべての式, すべての関数に型がある. 
 値の型は, その値が同じ型の別の値と何らかの性質を共有していることを示す. 
@@ -67,16 +74,17 @@
 
 型はプログラムに抽象をもたらす. 
 型を導入することで, 低水準の詳細を気にせずプログラミングが可能になる. 
-例えば, 値の型が文字列ならば, どのように実装されているかという細かいことは気にせず, 
+例えば, 値の型が文字列ならば, どのように実装されているかということを気にせず, 
 その文字列が他の文字列と同じように振る舞うとみなすことができる. 
 
+\subsubsection{型の定義と型検査}
 Haskell は静的型検査によりエラーを検出することができる. 
 Haskell では, 評価の際に型に起因するエラーが起きないことを保証している. 
-引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない. 
+例えば, 引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない. 
 Haskell は, すべての式, すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる. 
 
-エラーの検出の例として, Haskell で最もよく使われるデータ構造, リストで確認を行う. 
-また, リストの定義とあわせてデータ型の定義についても説明する. 
+エラーの検出の例として Haskell で最もよく使われるデータ構造であるリスト型で確認を行う. 
+また, リスト型の定義とあわせてデータ型の定義についても説明する. 
 
 リストとは, 角括弧で包まれた同じ型の要素の並びである. [1,2,3] などと表現する. 
 リストはソースコード\ref{src:list}のように定義されている. 
@@ -86,29 +94,35 @@
 \end{lstlisting}
 
 data というのは新しい型を定義する際に利用するキーワードである. 
-[] というのが型名である. 
+data キーワードのすぐ後にある [] a というのが型名である. 
 
-型名の右に a というのがあるが, これは多相型を表すのに使う型変数である. 
-型変数は様々な型を取ることができる.
-リストは, Intのリスト, Floatのリストといった様々な型のリストを作ることができ, 型変数を用いてそれを実現する. 
-型変数が何の型になるのかという情報は実行時には決まっており, Haskell の型安全を保つ. 
+a というのは, 型変数と呼ばれるものである.
+型変数は任意の型を取ることができる.
+リスト型は, Intのリスト, Floatのリストといった様々な型のリストを作ることができ, 型変数を用いてそれを実現する. 
+型変数が何の型になるのかという情報は実行時には決まっており, 関数に渡される際に型の不整合が起きることはない.
 
-= の右側が, 新しい型の定義である. 
+= の右側には, 新しい型の定義として型の値となるものを列挙する.
 $|$ は, もしくはという意味である. 
 つまりリストは, [] もしくは a : [a] という値になることが分かる. 
+
 [] は空リストを表す. 型名と同じであるが, 型とは名前領域が異なるため問題ない. 
 型名はプログラム中では注釈としてしか使われないためである. 
 
 a : [a] は再帰的なデータ構造である. 
-何らかの型の値 a を : で繋げて, 再度リストの定義を呼んでいる. 
+値 a を : で繋げて, 再度リストの定義を呼んでいる. 
 
-リストは無限に繋げることができ, リストの終端は空のリスト, つまり [] で終わる. 
-[1,2,3]という様にリストを表すが, これは単なるシンタックスシュガーであり, 
+この定義 [] $|$ a : [a] は,  a : a : a : .. : a : [] となり, a が任意個続いた後に, [] が来ることとなる.
+つまり, リストは無限に繋げることができ, リストの終端は空のリスト, つまり [] で終わる. 
+
+Haskell では, [1,2,3] という様にリストを表すが, これは単なるシンタックスシュガーであり, 
 内部では 1 : 2 : 3 : [] のように表現される. 
 
-リストは : を使うことで新しい要素を加えることができるが, 型変数は1つであり, 全ての要素は同じ型の要素である必要がある. 
+このように定義した型であっても, Haskell は型検査を行う.
+リストは : を使うことで新しい要素を加えることができるが, 全ての要素は同じ型の要素である必要がある. 
 違った型の要素を付け加えようとすると Haskell はコンパイル時にエラーを出す. 
 例えば, Int のリスト [3,4] に, 文字である 'b' を付け加えようとした場合エラーが発生する（ソースコード\ref{src:error}）. 
+型の定義に型変数を用いても Haskell は, [3,4] が何の型になるのかといった情報を推論する.
+そのため文字である 'b' をIntのリスト [3,4] に付け加えることはできない.
 
 \begin{lstlisting}[label=src:error, caption=Haskellのコンパイル時エラー]
 <interactive>:3:7:
@@ -120,7 +134,6 @@
 型検査でも捕まえられないエラーは存在する. 
 例えば, 式 "1 `div` 0" は, 型エラーではないが, 0 での除算は定義されていないので評価時にエラーとなる. 
 
-
 \subsubsection{型推論}
 Haskell は型推論を持つ. 
 型推論とは, 型の宣言をせずともそれを導くのに使われた関数の型シグネチャなどから自動的に型を決定する機構のことである. 
@@ -157,6 +170,7 @@
 Haskell では, プログラマが型の宣言を行わずとも, 型を推論し型安全を保つ. 
 しかし, 明示的な型宣言は可読性の向上や問題の発見に役に立つため, トップレベルの関数には型を明記することが一般的である. 
 
+\clearpage
 \section{モナド}
 Haskell では, さまざまな目的にモナドを使う. 
 I/O 処理を行うためには IO モナドを使う必要がある. 
@@ -167,7 +181,7 @@
 ある型クラスのインスタンスである型は, その型クラスに属する関数の集まりを実装する. 
 これは, それらの関数がその型ではどのような意味になるのか定義するということである. 
 
-モナドとなる型は, 型変数として具体型をただ１つ取る. 
+モナドとなる型は, 型変数として具体型をただ 1 つ取る. 
 これにより何かしらのコンテナに包まれた値を実現する. 
 モナドの振る舞いは型クラスとして実装し, 関数として return および $>>$= (bind) を定義する（ソースコード\ref{monad}）. 
 
@@ -229,7 +243,7 @@
 \end{lstlisting}
 
 instance Monad Maybe whereというのは, Maybe型をモナド型クラスのインスタンスとするのに使う構文である.
-その後実装すべき関数である return と $>>$= (bind) を定義していく. 
+モナド型クラスに属させるために必要な関数である return と $>>$= (bind) を, Maybeではどう振る舞うかを考え定義していく. 
 
 Maybe モナドの return は, 値をJustで包む. 
 これがコンテナに包む機能という意味である. 
@@ -250,8 +264,8 @@
 \end{lstlisting}
 
 関数 up と down を定義した. 
-up の場合, 引数として4が渡された場合, 上がれないため失敗, 
-down の場合, 引数として0が渡された場合, 下がれないため失敗と考える. 
+up の場合, 引数として4が渡された場合は上がれないため失敗, 
+down の場合, 引数として0が渡された場合は下がれないため失敗と考える. 
 
 3 という値にdown, down, up, up 繰り返していく時, モナドを使わない場合ソースコード\ref{src:up_without_monad}のように定義することになる. 
 
@@ -267,23 +281,25 @@
 
 \end{lstlisting}
 
-case 式は, caseとofの間の式を評価し, その値によっ評価を分岐させることができる. 
-case を受け取る $->$ の左の部分はパターンマッチを行うこともできる.  
-また, case は式のため, $->$ の右の部分の全ての型は一意である必要がある. 
-Haskell では分岐によって返ってくる値の型が異なるということはできない. 
+case 式は, caseとofの間の式を評価し, その値によって評価を分岐させるためのものである.
+case を受け取る $->$ の左の部分には式の値を書き, その式の値によって評価を分岐させる.
+例えば, 3 行目は down 3 の結果が Nothing なら, Nothing を返すという意味である.
+Justの場合, 値をplace1という変数に束縛しその後の処理を続ける.
 
-毎回, 失敗したか成功したか確認するために非常に煩雑なコードとなってしまった. 
-これを文脈を保ったまま, 関数を繋げられる モナドを使えばソースコード\ref{src:upmonad}のように記述できる. 
+ソースコード\ref{src:up_without_monad}では, 毎回失敗したか成功したか確認するために非常に煩雑なコードとなってしまった. 
+これを文脈を保ったまま, 関数を繋げられるモナドを使えばソースコード\ref{src:upmonad}のように記述できる. 
 
 \begin{lstlisting}[label=src:upmonad, caption=Maybeモナドを用いてupとdownを行う]
 return 3 >>= down >>= down >>= up >>= up
 \end{lstlisting}
 
-Maybe モナドを使うことで, この計算は失敗しているかもしれないという文脈を扱うことができる. 
+Maybe モナドを使うことで, この計算は失敗しているかもしれないという文脈を保ったまま処理を繋げていくことができる. 
 
 \subsubsection{IO モナド}
 Haskellで副作用を持つ処理を実行するには, IO モナドを利用する. 
-IO モナド自体は単なる命令書であり, 命令ではない. 
+IO モナドは, 処理系が現実世界に対する副作用に変換できるモナドである.
+
+IO モナド自体は, 「文字を1文字取ってくる」といった命令書である.
 bind を使って, 小さな命令書を合成して大きな命令書を作成できる. 
 最終的に, mainという名前をつけることで初めてランタイムにより実行される（ソースコード\ref{src:iomonad}）. 
 
@@ -300,10 +316,79 @@
 どんな状況においても同じ命令書を返すため, 副作用はない. 
 
 \clearpage
+\section{遅延評価}
+Haskell では, 必要となるまで式の評価が遅延される.
+Haskell の対話環境である GHCi でどのように評価されるか確認することができる.
+
+GHCiで評価を強制せずに値を表示する :sprint コマンドを使う.
+例えば, x を定義した後に :sprint コマンドを使うとソースコード\ref{src:sprint} のように表示される\footnote{GHCiでは, 関数や変数を定義する際にはletが必要となる.}.
+
+\begin{lstlisting}[label=src:sprint, caption=sprintコマンドの使用例]
+ghci> let x = 1 + 2
+ghci> :sprint x
+x = _
+\end{lstlisting}
+
+\_ は式が未評価であることを示している.
+Haskell ではこの未評価の部分を thunk と呼ぶ.
+
+\begin{lstlisting}[label=src:list_sprint, caption=リストの評価の様子]
+ghci> let y = map (+1) [1,2,3] :: [Int]
+ghci> :sprint y
+y = _
+ghci> length y
+3
+ghci> :sprint y
+y = [_,_,_]
+ghci> head y
+2
+ghci> :sprint y
+y = [2,_,_]
+\end{lstlisting}
+
+リストを使ってどのように評価されるのか確認する.
+ソースコード\ref{src:list_sprint} では, まずmap関数を利用してリストの要素を全て (+1) している.
+しかし, この計算は必要となるまで計算されない.
+直後にsprintを行うと, ただ\_が表示される.
+
+リストの長さを表示する関数であるlengthを実行後に sprint を行った場合は, 
+リストの要素数を確認しているため、要素数分のthunkを持つリストとなる.
+
+実際に値が必要となる関数を適用する.
+head はリストの先頭要素を取得する関数である.
+head を適用後に, sprint を行うと先頭要素だけが評価されたリストとなる.
+
+リストの例より, Haskell では本当に値が必要となるまで決して計算しないことが分かる.
+
+\subsubsection{引数のメモ化}
+
+Haskell の遅延評価では引数のメモ化を行う.
+ある関数の仮引数が, その関数の本体に複数回出現したとしても評価回数が1回のみである.
+例えば, ソースコード\ref{memo} は, 図 \ref{fig:memo} のようにメモ化される.
+y は未評価のthunkとして同じ x を参照する.
+そのため, x が2回評価されることはない.
+
+\newpage
+\begin{lstlisting}[label=memo, caption=メモ化]
+Prelude> let x = 1 + 2 :: Int
+Prelude> let y = (x,x)
+Prelude> :sprint y
+y = (_,_)
+\end{lstlisting}
+
+\begin{figure}[!htbp]
+ \begin{center}
+  \includegraphics[scale=0.6]{./images/memo.pdf}
+ \end{center}
+ \caption{メモ化の様子}
+ \label{fig:memo}
+\end{figure}
+
+\clearpage
 \section{並列実行}
 Haskellはデフォルトではシングルスレッドで走る. 
 並列に実行したい場合は, -threaded 付きでコンパイルし, RTS の -N オプションを付けて実行する. 
--N オプションで指定された数だけ, OSのスレッドが立ち上がり実行される. 
+-N オプションで指定された数だけ, OSのスレッドが立ち上がり実行される（ソースコード\ref{concurrent}）. 
 
 \begin{lstlisting}[language=bash, label=concurrent, caption=並列実行の様子]
 $ ghc -O2 par.hs -threaded
@@ -342,7 +427,12 @@
 Haskell のプログラムはmainという名前と実行したい関数を関連付けることで実行される. 
 今回は, print (runEval test)が実行される. 
 
-\begin{lstlisting}[label=eval, caption=Eval モナド]
+並列処理を行いたい箇所には, rpar を使う. 
+rpar の引数とした関数は並列に実行可能であることを示すことができる.
+Eval モナドの関数の型をみると, rpar は, a を モナドに包み, 逆にrunEval はモナドから a を取り出している（ソースコード\ref{eval}）.
+rpar で並列化可能計算を示したあと, runEvalで実行するという流れになる. 
+
+\begin{lstlisting}[label=eval, caption=Eval モナドの型]
 data Eval a
 instance Monad Eval
 
@@ -350,11 +440,6 @@
 rpar :: a -> Eval a
 \end{lstlisting}
 
-並列処理を行いたい箇所には, rpar を使う. 
-rpar の引数とした関数は並列に実行可能であることを示すことができる.
-Eval モナドの関数の型をみると, rpar は, a を モナドに包み, 逆にrunEval はモナドから a を取り出している. 
-rpar で並列化可能計算を示したあと, runEvalで実行するという流れになる. 
-
 rpar を利用している test 関数は rpar モナドをbindで接続しているが, 入れ子構造となり書き方は煩雑となっている. 
 Haskell にはモナドのために do 構文というシンタックスシュガーが用意されており, それを用いることでソースコード\ref{src:do}のように書くことができる. 
 do 構文を使うことでbindの入れ子構造を簡潔に書ける. 
@@ -391,7 +476,7 @@
 
 Haskell で並列実行を行いたい場合は, 遅延評価に気をつける必要がある. 
 rpar は単なるマーキングに過ぎず, rpar に渡したからといって直ちに並列実行が行われるわけではない.
-rpar で作成した Eval モナドを runEval に渡したあと、値が必要となるprintなどを行えば, 並列に実行可能な部分が並列に実行される. 
+rpar で作成した Eval モナドを runEval に渡したあと, 値が必要となるprintなどを行えば, 並列に実行可能な部分が並列に実行される. 
 
 また, rpar を使用する際, 別の計算の値に依存する計算がある場合, その2つの計算は並列実行できない. 
 例えば, ソースコード\ref{src:rpar}の場合は並列実行ができない.