Mercurial > hg > Papers > 2014 > toma-master
comparison paper/chapter1.tex @ 60:79d168016df4
add memorize
author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 11 Feb 2014 22:58:43 +0900 |
parents | 0a8d66c9ccd1 |
children | d11f4c6c7657 |
comparison
equal
deleted
inserted
replaced
59:0644825c43ac | 60:79d168016df4 |
---|---|
3 | 3 |
4 \section{純粋関数型プログラミング} | 4 \section{純粋関数型プログラミング} |
5 関数とは, 一つの引数を取り一つの結果を返す変換器のことである. | 5 関数とは, 一つの引数を取り一つの結果を返す変換器のことである. |
6 関数型プログラミング言語では, 関数を引数に適用させていくことで計算を行う. | 6 関数型プログラミング言語では, 関数を引数に適用させていくことで計算を行う. |
7 | 7 |
8 \subsubsection{関数の定義} | |
8 既存の手続き型言語と異なり, 手順を記述するのではなく, この関数が何であるかということを記述する. | 9 既存の手続き型言語と異なり, 手順を記述するのではなく, この関数が何であるかということを記述する. |
9 例えば, Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する. | 10 例えば, Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する. |
10 Haskell は, 関数を引数を適用するという考えに基づいて, 抽象的なプログラミングを可能とする. | 11 Haskell は, 関数を引数を適用するという考えに基づいて, 抽象的なプログラミングを可能とする. |
11 | 12 |
12 \begin{lstlisting}[label=src:fib, caption=フィボナッチ数列] | 13 \begin{lstlisting}[label=src:fib, caption=フィボナッチ数列] |
17 \end{lstlisting} | 18 \end{lstlisting} |
18 | 19 |
19 fib :: Int -$>$ Int は, 関数の型宣言である. | 20 fib :: Int -$>$ Int は, 関数の型宣言である. |
20 この関数は, Int を受け取って Int を返す関数ということを示す. | 21 この関数は, Int を受け取って Int を返す関数ということを示す. |
21 フィボナッチ数列の関数が三行に渡って書かれているが, これは Haskell のパターンマッチを活用している. | 22 フィボナッチ数列の関数が三行に渡って書かれているが, これは Haskell のパターンマッチを活用している. |
22 引数が 0 ならば 2 行目の fib が呼び出される. | 23 引数の値が 0 ならば 2 行目が呼び出され, 関数の結果は 0 となる. |
23 引数が 1 ならば 3 行目の fib が呼び出される. | 24 引数の値が 1 ならば 3 行目が呼び出され, 関数の結果は 1 となる. |
24 上から順に引数と一致する行がないか調べていき, 引数が 0 でも 1 でもなければ引数は n に束縛される. | 25 上から順に引数と一致する行がないか調べていき, 引数が 0 でも 1 でもなければ引数は n に束縛され, fib (n-2) + fib (n-1) が計算される. |
25 | 26 |
26 フィボナッチ数列の関数は, 自分自身を使って再帰的に定義している. | 27 フィボナッチ数列の関数は, 自分自身を使って再帰的に定義している. |
27 再帰は, 関数型プログラミング言語において必要不可欠な要素である. | 28 再帰は, 関数型プログラミング言語において必要不可欠な要素である. |
28 手続き型言語では, 配列とループを主に用いてプログラミングを行うが, Haskell ではリスト構造と再帰を用いる. | 29 手続き型言語では, 配列とループを主に用いてプログラミングを行うが Haskell ではリスト構造と再帰を用いる. |
29 | 30 |
31 \subsubsection{変数の代入} | |
30 純粋関数型プログラミングでは, 変数の代入は一度のみで後から書き換えることはできない. | 32 純粋関数型プログラミングでは, 変数の代入は一度のみで後から書き換えることはできない. |
31 フィボナッチ数列の関数でも, 一度引数を束縛した n を書き換えることはできない. | 33 フィボナッチ数列の関数でも, 一度引数を束縛した n を書き換えることはできない. |
32 関数にできることは, 何かを計算してその結果を返すことだけであり, 引数が同じならば関数は必ず同じ値を返すことが保証されている. | 34 関数にできることは, 何かを計算してその結果を返すことだけであり, 引数が同じならば関数は必ず同じ値を返すことが保証されている. |
33 この性質は関数の理解を容易にし, プログラムの証明を可能にする. | 35 この性質は関数の理解を容易にし, プログラムの証明を可能にする. |
34 正しいと分かる単純な関数を組み合わせて, より複雑な正しい関数を組み立てていくのが関数型言語のプログラミングスタイルである. | 36 正しいと分かる単純な関数を組み合わせて, より複雑な正しい関数を組み立てていくのが関数型言語のプログラミングスタイルである. |
35 | 37 |
38 \subsubsection{高階関数} | |
36 関数型プログラミング言語は, 関数を変数の値にすることができる. | 39 関数型プログラミング言語は, 関数を変数の値にすることができる. |
37 つまりこれは, 関数を第一級オブジェクトとして扱うことができるということである. | 40 これは, 関数を第一級オブジェクトとして扱うことができるということである. |
38 Haskell は, 引数として関数を取ったり返り値として関数を返すことができる高階関数を定義できる. | 41 Haskell は, 引数として関数を取ったり返り値として関数を返すことができる高階関数を定義できる. |
39 | 42 |
40 高階関数の例として Haskell のカリー化が挙げられる. | 43 高階関数の例として Haskell のカリー化が挙げられる. |
41 Haskell では, 全ての関数は一度に一つの引数だけを取る. | 44 Haskell では, 全ての関数は一度に一つの引数だけを取る. |
42 2 つのInt を受け取り, 大きい方を返す max の型はソースコード\ref{src:max}のように定義できる. | 45 2 つのInt を受け取り, 大きい方を返す max の型はソースコード\ref{src:max}のように定義できる. |
43 | 46 |
44 \begin{lstlisting}[label=src:max, caption=max関数] | 47 \begin{lstlisting}[label=src:max, caption=max関数] |
45 max :: Int -> Int -> Int | 48 max :: Int -> Int -> Int |
49 max x y = if x <= y | |
50 then y | |
51 else x | |
46 \end{lstlisting} | 52 \end{lstlisting} |
47 | 53 |
48 この関数定義に現れる-$>$は左結合である. | 54 この関数定義に現れる-$>$は左結合である. |
49 複数の引数を取るようにみえる関数は, 実際には1つの引数を取り, その次の引数を受け取る関数を返す(ソースコード\ref{src:max_curry}). | 55 複数の引数を取るようにみえる関数は, 実際には1つの引数を取り, その次の引数を受け取る関数を返す(ソースコード\ref{src:max_curry}). |
50 | 56 |
54 | 60 |
55 このように関数を返すことで全ての関数を一引数関数として表すことをカリー化という. | 61 このように関数を返すことで全ての関数を一引数関数として表すことをカリー化という. |
56 カリー化によって, 関数を本来より少ない引数で呼び出した際に部分適用された関数を得ることができる(ソースコード\ref{src:partial}). | 62 カリー化によって, 関数を本来より少ない引数で呼び出した際に部分適用された関数を得ることができる(ソースコード\ref{src:partial}). |
57 | 63 |
58 \begin{lstlisting}[label=src:partial, caption=関数の部分適用] | 64 \begin{lstlisting}[label=src:partial, caption=関数の部分適用] |
59 x = max 3 | 65 x = max 3 -- x は Int -> Int の関数 |
60 x 4 -- max 3 4 の結果として 4 が返される | 66 x 4 -- (max 3) 4 の結果として 4 が返される |
61 \end{lstlisting} | 67 \end{lstlisting} |
62 | 68 |
69 \clearpage | |
63 \section{型} | 70 \section{型} |
64 Haskell では, すべての式, すべての関数に型がある. | 71 Haskell では, すべての式, すべての関数に型がある. |
65 値の型は, その値が同じ型の別の値と何らかの性質を共有していることを示す. | 72 値の型は, その値が同じ型の別の値と何らかの性質を共有していることを示す. |
66 例えば, 数値は加算できる, 文字列は表示できるといった性質である. | 73 例えば, 数値は加算できる, 文字列は表示できるといった性質である. |
67 | 74 |
68 型はプログラムに抽象をもたらす. | 75 型はプログラムに抽象をもたらす. |
69 型を導入することで, 低水準の詳細を気にせずプログラミングが可能になる. | 76 型を導入することで, 低水準の詳細を気にせずプログラミングが可能になる. |
70 例えば, 値の型が文字列ならば, どのように実装されているかという細かいことは気にせず, | 77 例えば, 値の型が文字列ならば, どのように実装されているかということを気にせず, |
71 その文字列が他の文字列と同じように振る舞うとみなすことができる. | 78 その文字列が他の文字列と同じように振る舞うとみなすことができる. |
72 | 79 |
80 \subsubsection{型の定義と型検査} | |
73 Haskell は静的型検査によりエラーを検出することができる. | 81 Haskell は静的型検査によりエラーを検出することができる. |
74 Haskell では, 評価の際に型に起因するエラーが起きないことを保証している. | 82 Haskell では, 評価の際に型に起因するエラーが起きないことを保証している. |
75 引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない. | 83 例えば, 引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない. |
76 Haskell は, すべての式, すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる. | 84 Haskell は, すべての式, すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる. |
77 | 85 |
78 エラーの検出の例として, Haskell で最もよく使われるデータ構造, リストで確認を行う. | 86 エラーの検出の例として Haskell で最もよく使われるデータ構造であるリスト型で確認を行う. |
79 また, リストの定義とあわせてデータ型の定義についても説明する. | 87 また, リスト型の定義とあわせてデータ型の定義についても説明する. |
80 | 88 |
81 リストとは, 角括弧で包まれた同じ型の要素の並びである. [1,2,3] などと表現する. | 89 リストとは, 角括弧で包まれた同じ型の要素の並びである. [1,2,3] などと表現する. |
82 リストはソースコード\ref{src:list}のように定義されている. | 90 リストはソースコード\ref{src:list}のように定義されている. |
83 | 91 |
84 \begin{lstlisting}[label=src:list, caption=Haskellのリスト定義] | 92 \begin{lstlisting}[label=src:list, caption=Haskellのリスト定義] |
85 data [] a = [] | a : [a] | 93 data [] a = [] | a : [a] |
86 \end{lstlisting} | 94 \end{lstlisting} |
87 | 95 |
88 data というのは新しい型を定義する際に利用するキーワードである. | 96 data というのは新しい型を定義する際に利用するキーワードである. |
89 [] というのが型名である. | 97 data キーワードのすぐ後にある [] a というのが型名である. |
90 | 98 |
91 型名の右に a というのがあるが, これは多相型を表すのに使う型変数である. | 99 a というのは, 型変数と呼ばれるものである. |
92 型変数は様々な型を取ることができる. | 100 型変数は任意の型を取ることができる. |
93 リストは, Intのリスト, Floatのリストといった様々な型のリストを作ることができ, 型変数を用いてそれを実現する. | 101 リスト型は, Intのリスト, Floatのリストといった様々な型のリストを作ることができ, 型変数を用いてそれを実現する. |
94 型変数が何の型になるのかという情報は実行時には決まっており, Haskell の型安全を保つ. | 102 型変数が何の型になるのかという情報は実行時には決まっており, 関数に渡される際に型の不整合が起きることはない. |
95 | 103 |
96 = の右側が, 新しい型の定義である. | 104 = の右側には, 新しい型の定義として型の値となるものを列挙する. |
97 $|$ は, もしくはという意味である. | 105 $|$ は, もしくはという意味である. |
98 つまりリストは, [] もしくは a : [a] という値になることが分かる. | 106 つまりリストは, [] もしくは a : [a] という値になることが分かる. |
107 | |
99 [] は空リストを表す. 型名と同じであるが, 型とは名前領域が異なるため問題ない. | 108 [] は空リストを表す. 型名と同じであるが, 型とは名前領域が異なるため問題ない. |
100 型名はプログラム中では注釈としてしか使われないためである. | 109 型名はプログラム中では注釈としてしか使われないためである. |
101 | 110 |
102 a : [a] は再帰的なデータ構造である. | 111 a : [a] は再帰的なデータ構造である. |
103 何らかの型の値 a を : で繋げて, 再度リストの定義を呼んでいる. | 112 値 a を : で繋げて, 再度リストの定義を呼んでいる. |
104 | 113 |
105 リストは無限に繋げることができ, リストの終端は空のリスト, つまり [] で終わる. | 114 この定義 [] $|$ a : [a] は, a : a : a : .. : a : [] となり, a が任意個続いた後に, [] が来ることとなる. |
106 [1,2,3]という様にリストを表すが, これは単なるシンタックスシュガーであり, | 115 つまり, リストは無限に繋げることができ, リストの終端は空のリスト, つまり [] で終わる. |
116 | |
117 Haskell では, [1,2,3] という様にリストを表すが, これは単なるシンタックスシュガーであり, | |
107 内部では 1 : 2 : 3 : [] のように表現される. | 118 内部では 1 : 2 : 3 : [] のように表現される. |
108 | 119 |
109 リストは : を使うことで新しい要素を加えることができるが, 型変数は1つであり, 全ての要素は同じ型の要素である必要がある. | 120 このように定義した型であっても, Haskell は型検査を行う. |
121 リストは : を使うことで新しい要素を加えることができるが, 全ての要素は同じ型の要素である必要がある. | |
110 違った型の要素を付け加えようとすると Haskell はコンパイル時にエラーを出す. | 122 違った型の要素を付け加えようとすると Haskell はコンパイル時にエラーを出す. |
111 例えば, Int のリスト [3,4] に, 文字である 'b' を付け加えようとした場合エラーが発生する(ソースコード\ref{src:error}). | 123 例えば, Int のリスト [3,4] に, 文字である 'b' を付け加えようとした場合エラーが発生する(ソースコード\ref{src:error}). |
124 型の定義に型変数を用いても Haskell は, [3,4] が何の型になるのかといった情報を推論する. | |
125 そのため文字である 'b' をIntのリスト [3,4] に付け加えることはできない. | |
112 | 126 |
113 \begin{lstlisting}[label=src:error, caption=Haskellのコンパイル時エラー] | 127 \begin{lstlisting}[label=src:error, caption=Haskellのコンパイル時エラー] |
114 <interactive>:3:7: | 128 <interactive>:3:7: |
115 Couldn't match type `Int' with `Char' | 129 Couldn't match type `Int' with `Char' |
116 Expected type: [Char] | 130 Expected type: [Char] |
118 \end{lstlisting} | 132 \end{lstlisting} |
119 | 133 |
120 型検査でも捕まえられないエラーは存在する. | 134 型検査でも捕まえられないエラーは存在する. |
121 例えば, 式 "1 `div` 0" は, 型エラーではないが, 0 での除算は定義されていないので評価時にエラーとなる. | 135 例えば, 式 "1 `div` 0" は, 型エラーではないが, 0 での除算は定義されていないので評価時にエラーとなる. |
122 | 136 |
123 | |
124 \subsubsection{型推論} | 137 \subsubsection{型推論} |
125 Haskell は型推論を持つ. | 138 Haskell は型推論を持つ. |
126 型推論とは, 型の宣言をせずともそれを導くのに使われた関数の型シグネチャなどから自動的に型を決定する機構のことである. | 139 型推論とは, 型の宣言をせずともそれを導くのに使われた関数の型シグネチャなどから自動的に型を決定する機構のことである. |
127 型推論のない静的型付け言語は, プログラマが型の宣言を行うことが強制されるが Haskell では型の宣言は必須ではない. | 140 型推論のない静的型付け言語は, プログラマが型の宣言を行うことが強制されるが Haskell では型の宣言は必須ではない. |
128 | 141 |
155 返り値となる型は, elemsの[a]となる. このaは, elemsが受け取るMapの2つ目の型と一致するため, childrenの返り値であるMap Int Node より, [Node]ということが分かる. | 168 返り値となる型は, elemsの[a]となる. このaは, elemsが受け取るMapの2つ目の型と一致するため, childrenの返り値であるMap Int Node より, [Node]ということが分かる. |
156 | 169 |
157 Haskell では, プログラマが型の宣言を行わずとも, 型を推論し型安全を保つ. | 170 Haskell では, プログラマが型の宣言を行わずとも, 型を推論し型安全を保つ. |
158 しかし, 明示的な型宣言は可読性の向上や問題の発見に役に立つため, トップレベルの関数には型を明記することが一般的である. | 171 しかし, 明示的な型宣言は可読性の向上や問題の発見に役に立つため, トップレベルの関数には型を明記することが一般的である. |
159 | 172 |
173 \clearpage | |
160 \section{モナド} | 174 \section{モナド} |
161 Haskell では, さまざまな目的にモナドを使う. | 175 Haskell では, さまざまな目的にモナドを使う. |
162 I/O 処理を行うためには IO モナドを使う必要がある. | 176 I/O 処理を行うためには IO モナドを使う必要がある. |
163 プログラミングを行うにあたり, I/O 処理は欠かせないため, モナドの説明を行う. | 177 プログラミングを行うにあたり, I/O 処理は欠かせないため, モナドの説明を行う. |
164 | 178 |
165 モナドとは, 型クラスの 1 つである. | 179 モナドとは, 型クラスの 1 つである. |
166 型クラスは型の振る舞いを定義するものである. | 180 型クラスは型の振る舞いを定義するものである. |
167 ある型クラスのインスタンスである型は, その型クラスに属する関数の集まりを実装する. | 181 ある型クラスのインスタンスである型は, その型クラスに属する関数の集まりを実装する. |
168 これは, それらの関数がその型ではどのような意味になるのか定義するということである. | 182 これは, それらの関数がその型ではどのような意味になるのか定義するということである. |
169 | 183 |
170 モナドとなる型は, 型変数として具体型をただ1つ取る. | 184 モナドとなる型は, 型変数として具体型をただ 1 つ取る. |
171 これにより何かしらのコンテナに包まれた値を実現する. | 185 これにより何かしらのコンテナに包まれた値を実現する. |
172 モナドの振る舞いは型クラスとして実装し, 関数として return および $>>$= (bind) を定義する(ソースコード\ref{monad}). | 186 モナドの振る舞いは型クラスとして実装し, 関数として return および $>>$= (bind) を定義する(ソースコード\ref{monad}). |
173 | 187 |
174 \begin{lstlisting}[label=monad, caption=モナドに属する関数の型] | 188 \begin{lstlisting}[label=monad, caption=モナドに属する関数の型] |
175 return :: Monad m => a -> m a | 189 return :: Monad m => a -> m a |
227 Nothing >>= f = Nothing | 241 Nothing >>= f = Nothing |
228 Just x >>= f = f x | 242 Just x >>= f = f x |
229 \end{lstlisting} | 243 \end{lstlisting} |
230 | 244 |
231 instance Monad Maybe whereというのは, Maybe型をモナド型クラスのインスタンスとするのに使う構文である. | 245 instance Monad Maybe whereというのは, Maybe型をモナド型クラスのインスタンスとするのに使う構文である. |
232 その後実装すべき関数である return と $>>$= (bind) を定義していく. | 246 モナド型クラスに属させるために必要な関数である return と $>>$= (bind) を, Maybeではどう振る舞うかを考え定義していく. |
233 | 247 |
234 Maybe モナドの return は, 値をJustで包む. | 248 Maybe モナドの return は, 値をJustで包む. |
235 これがコンテナに包む機能という意味である. | 249 これがコンテナに包む機能という意味である. |
236 | 250 |
237 $>>$= (bind) は, 「コンテナに包まれた値」と, 「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり, コンテナに包まれた値をその関数に適用すると説明した. | 251 $>>$= (bind) は, 「コンテナに包まれた値」と, 「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり, コンテナに包まれた値をその関数に適用すると説明した. |
248 down 0 = Nothing | 262 down 0 = Nothing |
249 down n = Just (n - 1) | 263 down n = Just (n - 1) |
250 \end{lstlisting} | 264 \end{lstlisting} |
251 | 265 |
252 関数 up と down を定義した. | 266 関数 up と down を定義した. |
253 up の場合, 引数として4が渡された場合, 上がれないため失敗, | 267 up の場合, 引数として4が渡された場合は上がれないため失敗, |
254 down の場合, 引数として0が渡された場合, 下がれないため失敗と考える. | 268 down の場合, 引数として0が渡された場合は下がれないため失敗と考える. |
255 | 269 |
256 3 という値にdown, down, up, up 繰り返していく時, モナドを使わない場合ソースコード\ref{src:up_without_monad}のように定義することになる. | 270 3 という値にdown, down, up, up 繰り返していく時, モナドを使わない場合ソースコード\ref{src:up_without_monad}のように定義することになる. |
257 | 271 |
258 \begin{lstlisting}[label=src:up_without_monad, caption=Maybeモナドを使わずにupとdownを行う] | 272 \begin{lstlisting}[label=src:up_without_monad, caption=Maybeモナドを使わずにupとdownを行う] |
259 updown :: Maybe Int | 273 updown :: Maybe Int |
265 Nothing -> Nothing | 279 Nothing -> Nothing |
266 Just place3 -> up place3 | 280 Just place3 -> up place3 |
267 | 281 |
268 \end{lstlisting} | 282 \end{lstlisting} |
269 | 283 |
270 case 式は, caseとofの間の式を評価し, その値によっ評価を分岐させることができる. | 284 case 式は, caseとofの間の式を評価し, その値によって評価を分岐させるためのものである. |
271 case を受け取る $->$ の左の部分はパターンマッチを行うこともできる. | 285 case を受け取る $->$ の左の部分には式の値を書き, その式の値によって評価を分岐させる. |
272 また, case は式のため, $->$ の右の部分の全ての型は一意である必要がある. | 286 例えば, 3 行目は down 3 の結果が Nothing なら, Nothing を返すという意味である. |
273 Haskell では分岐によって返ってくる値の型が異なるということはできない. | 287 Justの場合, 値をplace1という変数に束縛しその後の処理を続ける. |
274 | 288 |
275 毎回, 失敗したか成功したか確認するために非常に煩雑なコードとなってしまった. | 289 ソースコード\ref{src:up_without_monad}では, 毎回失敗したか成功したか確認するために非常に煩雑なコードとなってしまった. |
276 これを文脈を保ったまま, 関数を繋げられる モナドを使えばソースコード\ref{src:upmonad}のように記述できる. | 290 これを文脈を保ったまま, 関数を繋げられるモナドを使えばソースコード\ref{src:upmonad}のように記述できる. |
277 | 291 |
278 \begin{lstlisting}[label=src:upmonad, caption=Maybeモナドを用いてupとdownを行う] | 292 \begin{lstlisting}[label=src:upmonad, caption=Maybeモナドを用いてupとdownを行う] |
279 return 3 >>= down >>= down >>= up >>= up | 293 return 3 >>= down >>= down >>= up >>= up |
280 \end{lstlisting} | 294 \end{lstlisting} |
281 | 295 |
282 Maybe モナドを使うことで, この計算は失敗しているかもしれないという文脈を扱うことができる. | 296 Maybe モナドを使うことで, この計算は失敗しているかもしれないという文脈を保ったまま処理を繋げていくことができる. |
283 | 297 |
284 \subsubsection{IO モナド} | 298 \subsubsection{IO モナド} |
285 Haskellで副作用を持つ処理を実行するには, IO モナドを利用する. | 299 Haskellで副作用を持つ処理を実行するには, IO モナドを利用する. |
286 IO モナド自体は単なる命令書であり, 命令ではない. | 300 IO モナドは, 処理系が現実世界に対する副作用に変換できるモナドである. |
301 | |
302 IO モナド自体は, 「文字を1文字取ってくる」といった命令書である. | |
287 bind を使って, 小さな命令書を合成して大きな命令書を作成できる. | 303 bind を使って, 小さな命令書を合成して大きな命令書を作成できる. |
288 最終的に, mainという名前をつけることで初めてランタイムにより実行される(ソースコード\ref{src:iomonad}). | 304 最終的に, mainという名前をつけることで初めてランタイムにより実行される(ソースコード\ref{src:iomonad}). |
289 | 305 |
290 \begin{lstlisting}[label=src:iomonad, caption=Hello Worldと出力] | 306 \begin{lstlisting}[label=src:iomonad, caption=Hello Worldと出力] |
291 main :: IO () | 307 main :: IO () |
298 呼び出した状況によって, 返ってくるノードが違うため副作用があるようにみえる. | 314 呼び出した状況によって, 返ってくるノードが違うため副作用があるようにみえる. |
299 しかし, 実際にこの関数が返すのは, 「ノードを取得する」という命令書である. | 315 しかし, 実際にこの関数が返すのは, 「ノードを取得する」という命令書である. |
300 どんな状況においても同じ命令書を返すため, 副作用はない. | 316 どんな状況においても同じ命令書を返すため, 副作用はない. |
301 | 317 |
302 \clearpage | 318 \clearpage |
319 \section{遅延評価} | |
320 Haskell では, 必要となるまで式の評価が遅延される. | |
321 Haskell の対話環境である GHCi でどのように評価されるか確認することができる. | |
322 | |
323 GHCiで評価を強制せずに値を表示する :sprint コマンドを使う. | |
324 例えば, x を定義した後に :sprint コマンドを使うとソースコード\ref{src:sprint} のように表示される\footnote{GHCiでは, 関数や変数を定義する際にはletが必要となる.}. | |
325 | |
326 \begin{lstlisting}[label=src:sprint, caption=sprintコマンドの使用例] | |
327 ghci> let x = 1 + 2 | |
328 ghci> :sprint x | |
329 x = _ | |
330 \end{lstlisting} | |
331 | |
332 \_ は式が未評価であることを示している. | |
333 Haskell ではこの未評価の部分を thunk と呼ぶ. | |
334 | |
335 \begin{lstlisting}[label=src:list_sprint, caption=リストの評価の様子] | |
336 ghci> let y = map (+1) [1,2,3] :: [Int] | |
337 ghci> :sprint y | |
338 y = _ | |
339 ghci> length y | |
340 3 | |
341 ghci> :sprint y | |
342 y = [_,_,_] | |
343 ghci> head y | |
344 2 | |
345 ghci> :sprint y | |
346 y = [2,_,_] | |
347 \end{lstlisting} | |
348 | |
349 リストを使ってどのように評価されるのか確認する. | |
350 ソースコード\ref{src:list_sprint} では, まずmap関数を利用してリストの要素を全て (+1) している. | |
351 しかし, この計算は必要となるまで計算されない. | |
352 直後にsprintを行うと, ただ\_が表示される. | |
353 | |
354 リストの長さを表示する関数であるlengthを実行後に sprint を行った場合は, | |
355 リストの要素数を確認しているため、要素数分のthunkを持つリストとなる. | |
356 | |
357 実際に値が必要となる関数を適用する. | |
358 head はリストの先頭要素を取得する関数である. | |
359 head を適用後に, sprint を行うと先頭要素だけが評価されたリストとなる. | |
360 | |
361 リストの例より, Haskell では本当に値が必要となるまで決して計算しないことが分かる. | |
362 | |
363 \subsubsection{引数のメモ化} | |
364 | |
365 Haskell の遅延評価では引数のメモ化を行う. | |
366 ある関数の仮引数が, その関数の本体に複数回出現したとしても評価回数が1回のみである. | |
367 例えば, ソースコード\ref{memo} は, 図 \ref{fig:memo} のようにメモ化される. | |
368 y は未評価のthunkとして同じ x を参照する. | |
369 そのため, x が2回評価されることはない. | |
370 | |
371 \newpage | |
372 \begin{lstlisting}[label=memo, caption=メモ化] | |
373 Prelude> let x = 1 + 2 :: Int | |
374 Prelude> let y = (x,x) | |
375 Prelude> :sprint y | |
376 y = (_,_) | |
377 \end{lstlisting} | |
378 | |
379 \begin{figure}[!htbp] | |
380 \begin{center} | |
381 \includegraphics[scale=0.6]{./images/memo.pdf} | |
382 \end{center} | |
383 \caption{メモ化の様子} | |
384 \label{fig:memo} | |
385 \end{figure} | |
386 | |
387 \clearpage | |
303 \section{並列実行} | 388 \section{並列実行} |
304 Haskellはデフォルトではシングルスレッドで走る. | 389 Haskellはデフォルトではシングルスレッドで走る. |
305 並列に実行したい場合は, -threaded 付きでコンパイルし, RTS の -N オプションを付けて実行する. | 390 並列に実行したい場合は, -threaded 付きでコンパイルし, RTS の -N オプションを付けて実行する. |
306 -N オプションで指定された数だけ, OSのスレッドが立ち上がり実行される. | 391 -N オプションで指定された数だけ, OSのスレッドが立ち上がり実行される(ソースコード\ref{concurrent}). |
307 | 392 |
308 \begin{lstlisting}[language=bash, label=concurrent, caption=並列実行の様子] | 393 \begin{lstlisting}[language=bash, label=concurrent, caption=並列実行の様子] |
309 $ ghc -O2 par.hs -threaded | 394 $ ghc -O2 par.hs -threaded |
310 $ ./par +RTS -N2 | 395 $ ./par +RTS -N2 |
311 \end{lstlisting} | 396 \end{lstlisting} |
340 まず, Eval モナドが定義された, Control.Parallel.Strategies をロードし, Eval モナドを利用できるようにしている. | 425 まず, Eval モナドが定義された, Control.Parallel.Strategies をロードし, Eval モナドを利用できるようにしている. |
341 | 426 |
342 Haskell のプログラムはmainという名前と実行したい関数を関連付けることで実行される. | 427 Haskell のプログラムはmainという名前と実行したい関数を関連付けることで実行される. |
343 今回は, print (runEval test)が実行される. | 428 今回は, print (runEval test)が実行される. |
344 | 429 |
345 \begin{lstlisting}[label=eval, caption=Eval モナド] | 430 並列処理を行いたい箇所には, rpar を使う. |
431 rpar の引数とした関数は並列に実行可能であることを示すことができる. | |
432 Eval モナドの関数の型をみると, rpar は, a を モナドに包み, 逆にrunEval はモナドから a を取り出している(ソースコード\ref{eval}). | |
433 rpar で並列化可能計算を示したあと, runEvalで実行するという流れになる. | |
434 | |
435 \begin{lstlisting}[label=eval, caption=Eval モナドの型] | |
346 data Eval a | 436 data Eval a |
347 instance Monad Eval | 437 instance Monad Eval |
348 | 438 |
349 runEval :: Eval a -> a | 439 runEval :: Eval a -> a |
350 rpar :: a -> Eval a | 440 rpar :: a -> Eval a |
351 \end{lstlisting} | 441 \end{lstlisting} |
352 | |
353 並列処理を行いたい箇所には, rpar を使う. | |
354 rpar の引数とした関数は並列に実行可能であることを示すことができる. | |
355 Eval モナドの関数の型をみると, rpar は, a を モナドに包み, 逆にrunEval はモナドから a を取り出している. | |
356 rpar で並列化可能計算を示したあと, runEvalで実行するという流れになる. | |
357 | 442 |
358 rpar を利用している test 関数は rpar モナドをbindで接続しているが, 入れ子構造となり書き方は煩雑となっている. | 443 rpar を利用している test 関数は rpar モナドをbindで接続しているが, 入れ子構造となり書き方は煩雑となっている. |
359 Haskell にはモナドのために do 構文というシンタックスシュガーが用意されており, それを用いることでソースコード\ref{src:do}のように書くことができる. | 444 Haskell にはモナドのために do 構文というシンタックスシュガーが用意されており, それを用いることでソースコード\ref{src:do}のように書くことができる. |
360 do 構文を使うことでbindの入れ子構造を簡潔に書ける. | 445 do 構文を使うことでbindの入れ子構造を簡潔に書ける. |
361 | 446 |
389 main = print (fst (runEval test)) | 474 main = print (fst (runEval test)) |
390 \end{lstlisting} | 475 \end{lstlisting} |
391 | 476 |
392 Haskell で並列実行を行いたい場合は, 遅延評価に気をつける必要がある. | 477 Haskell で並列実行を行いたい場合は, 遅延評価に気をつける必要がある. |
393 rpar は単なるマーキングに過ぎず, rpar に渡したからといって直ちに並列実行が行われるわけではない. | 478 rpar は単なるマーキングに過ぎず, rpar に渡したからといって直ちに並列実行が行われるわけではない. |
394 rpar で作成した Eval モナドを runEval に渡したあと、値が必要となるprintなどを行えば, 並列に実行可能な部分が並列に実行される. | 479 rpar で作成した Eval モナドを runEval に渡したあと, 値が必要となるprintなどを行えば, 並列に実行可能な部分が並列に実行される. |
395 | 480 |
396 また, rpar を使用する際, 別の計算の値に依存する計算がある場合, その2つの計算は並列実行できない. | 481 また, rpar を使用する際, 別の計算の値に依存する計算がある場合, その2つの計算は並列実行できない. |
397 例えば, ソースコード\ref{src:rpar}の場合は並列実行ができない. | 482 例えば, ソースコード\ref{src:rpar}の場合は並列実行ができない. |
398 | 483 |
399 \begin{lstlisting}[label=src:rpar, caption=前の計算に依存した計算] | 484 \begin{lstlisting}[label=src:rpar, caption=前の計算に依存した計算] |