annotate 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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6
37efb7dc0bda describe introduciton
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
1 \chapter{Haskellとは} \label{ch:haskell}
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
2  Haskell とは純粋関数型プログラミング言語である.
2
d8b94e828d79 add tex files
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3
15
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
4 \section{純粋関数型プログラミング}
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
5 関数とは, 一つの引数を取り一つの結果を返す変換器のことである.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
6 関数型プログラミング言語では, 関数を引数に適用させていくことで計算を行う.
15
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
7
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
8 \subsubsection{関数の定義}
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
9 既存の手続き型言語と異なり, 手順を記述するのではなく, この関数が何であるかということを記述する.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
10 例えば, Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
11 Haskell は, 関数を引数を適用するという考えに基づいて, 抽象的なプログラミングを可能とする.
7
f354d23bd80d describe 2.1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
12
15
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
13 \begin{lstlisting}[label=src:fib, caption=フィボナッチ数列]
34
345eacdf29e4 add apendix
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
14 fib :: Int -> Int
15
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
15 fib 0 = 0
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
16 fib 1 = 1
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
17 fib n = fib (n-2) + fib (n-1)
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
18 \end{lstlisting}
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
19
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
20 fib :: Int -$>$ Int は, 関数の型宣言である.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
21 この関数は, Int を受け取って Int を返す関数ということを示す.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
22 フィボナッチ数列の関数が三行に渡って書かれているが, これは Haskell のパターンマッチを活用している.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
23 引数の値が 0 ならば 2 行目が呼び出され, 関数の結果は 0 となる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
24 引数の値が 1 ならば 3 行目が呼び出され, 関数の結果は 1 となる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
25 上から順に引数と一致する行がないか調べていき, 引数が 0 でも 1 でもなければ引数は n に束縛され, fib (n-2) + fib (n-1) が計算される.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
26
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
27 フィボナッチ数列の関数は, 自分自身を使って再帰的に定義している.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
28 再帰は, 関数型プログラミング言語において必要不可欠な要素である.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
29 手続き型言語では, 配列とループを主に用いてプログラミングを行うが Haskell ではリスト構造と再帰を用いる.
15
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
30
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
31 \subsubsection{変数の代入}
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
32 純粋関数型プログラミングでは, 変数の代入は一度のみで後から書き換えることはできない.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
33 フィボナッチ数列の関数でも, 一度引数を束縛した n を書き換えることはできない.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
34 関数にできることは, 何かを計算してその結果を返すことだけであり, 引数が同じならば関数は必ず同じ値を返すことが保証されている.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
35 この性質は関数の理解を容易にし, プログラムの証明を可能にする.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
36 正しいと分かる単純な関数を組み合わせて, より複雑な正しい関数を組み立てていくのが関数型言語のプログラミングスタイルである.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
37
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
38 \subsubsection{高階関数}
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
39 関数型プログラミング言語は, 関数を変数の値にすることができる.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
40 これは, 関数を第一級オブジェクトとして扱うことができるということである.
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
41 Haskell は, 引数として関数を取ったり返り値として関数を返すことができる高階関数を定義できる.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
42
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
43 高階関数の例として Haskell のカリー化が挙げられる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
44 Haskell では, 全ての関数は一度に一つの引数だけを取る.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
45 2 つのInt を受け取り, 大きい方を返す max の型はソースコード\ref{src:max}のように定義できる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
46
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
47 \begin{lstlisting}[label=src:max, caption=max関数]
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
48 max :: Int -> Int -> Int
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
49 max x y = if x <= y
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
50 then y
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
51 else x
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
52 \end{lstlisting}
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
53
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
54 この関数定義に現れる-$>$は左結合である.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
55 複数の引数を取るようにみえる関数は, 実際には1つの引数を取り, その次の引数を受け取る関数を返す(ソースコード\ref{src:max_curry}).
7
f354d23bd80d describe 2.1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
56
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
57 \begin{lstlisting}[label=src:max_curry, caption=max関数のカリー化]
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
58 max :: Int -> (Int -> Int)
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
59 \end{lstlisting}
7
f354d23bd80d describe 2.1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
60
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
61 このように関数を返すことで全ての関数を一引数関数として表すことをカリー化という.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
62 カリー化によって, 関数を本来より少ない引数で呼び出した際に部分適用された関数を得ることができる(ソースコード\ref{src:partial}).
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
63
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
64 \begin{lstlisting}[label=src:partial, caption=関数の部分適用]
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
65 x = max 3 -- x は Int -> Int の関数
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
66 x 4 -- (max 3) 4 の結果として 4 が返される
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
67 \end{lstlisting}
7
f354d23bd80d describe 2.1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
68
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
69 \clearpage
7
f354d23bd80d describe 2.1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
70 \section{型}
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
71 Haskell では, すべての式, すべての関数に型がある.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
72 値の型は, その値が同じ型の別の値と何らかの性質を共有していることを示す.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
73 例えば, 数値は加算できる, 文字列は表示できるといった性質である.
15
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
74
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
75 型はプログラムに抽象をもたらす.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
76 型を導入することで, 低水準の詳細を気にせずプログラミングが可能になる.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
77 例えば, 値の型が文字列ならば, どのように実装されているかということを気にせず,
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
78 その文字列が他の文字列と同じように振る舞うとみなすことができる.
15
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
79
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
80 \subsubsection{型の定義と型検査}
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
81 Haskell は静的型検査によりエラーを検出することができる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
82 Haskell では, 評価の際に型に起因するエラーが起きないことを保証している.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
83 例えば, 引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない.
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
84 Haskell は, すべての式, すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる.
15
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
85
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
86 エラーの検出の例として Haskell で最もよく使われるデータ構造であるリスト型で確認を行う.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
87 また, リスト型の定義とあわせてデータ型の定義についても説明する.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
88
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
89 リストとは, 角括弧で包まれた同じ型の要素の並びである. [1,2,3] などと表現する.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
90 リストはソースコード\ref{src:list}のように定義されている.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
91
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
92 \begin{lstlisting}[label=src:list, caption=Haskellのリスト定義]
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
93 data [] a = [] | a : [a]
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
94 \end{lstlisting}
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
95
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
96 data というのは新しい型を定義する際に利用するキーワードである.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
97 data キーワードのすぐ後にある [] a というのが型名である.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
98
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
99 a というのは, 型変数と呼ばれるものである.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
100 型変数は任意の型を取ることができる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
101 リスト型は, Intのリスト, Floatのリストといった様々な型のリストを作ることができ, 型変数を用いてそれを実現する.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
102 型変数が何の型になるのかという情報は実行時には決まっており, 関数に渡される際に型の不整合が起きることはない.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
103
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
104 = の右側には, 新しい型の定義として型の値となるものを列挙する.
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
105 $|$ は, もしくはという意味である.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
106 つまりリストは, [] もしくは a : [a] という値になることが分かる.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
107
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
108 [] は空リストを表す. 型名と同じであるが, 型とは名前領域が異なるため問題ない.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
109 型名はプログラム中では注釈としてしか使われないためである.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
110
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
111 a : [a] は再帰的なデータ構造である.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
112 値 a を : で繋げて, 再度リストの定義を呼んでいる.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
113
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
114 この定義 [] $|$ a : [a] は, a : a : a : .. : a : [] となり, a が任意個続いた後に, [] が来ることとなる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
115 つまり, リストは無限に繋げることができ, リストの終端は空のリスト, つまり [] で終わる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
116
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
117 Haskell では, [1,2,3] という様にリストを表すが, これは単なるシンタックスシュガーであり,
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
118 内部では 1 : 2 : 3 : [] のように表現される.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
119
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
120 このように定義した型であっても, Haskell は型検査を行う.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
121 リストは : を使うことで新しい要素を加えることができるが, 全ての要素は同じ型の要素である必要がある.
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
122 違った型の要素を付け加えようとすると Haskell はコンパイル時にエラーを出す.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
123 例えば, Int のリスト [3,4] に, 文字である 'b' を付け加えようとした場合エラーが発生する(ソースコード\ref{src:error}).
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
124 型の定義に型変数を用いても Haskell は, [3,4] が何の型になるのかといった情報を推論する.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
125 そのため文字である 'b' をIntのリスト [3,4] に付け加えることはできない.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
126
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
127 \begin{lstlisting}[label=src:error, caption=Haskellのコンパイル時エラー]
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
128 <interactive>:3:7:
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
129 Couldn't match type `Int' with `Char'
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
130 Expected type: [Char]
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
131 Actual type: [Int]
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
132 \end{lstlisting}
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
133
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
134 型検査でも捕まえられないエラーは存在する.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
135 例えば, 式 "1 `div` 0" は, 型エラーではないが, 0 での除算は定義されていないので評価時にエラーとなる.
15
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
136
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
137 \subsubsection{型推論}
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
138 Haskell は型推論を持つ.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
139 型推論とは, 型の宣言をせずともそれを導くのに使われた関数の型シグネチャなどから自動的に型を決定する機構のことである.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
140 型推論のない静的型付け言語は, プログラマが型の宣言を行うことが強制されるが Haskell では型の宣言は必須ではない.
15
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
141
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
142 例として, 開発したデータベースで実装した getChildren という関数に対して型推論を行ってみる(ソースコード\ref{src:getchildren}).
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
143
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
144 \begin{lstlisting}[label=src:getchildren, caption=getChildren関数]
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
145 getChildren node path = elems (children (getNode node path))
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
146 \end{lstlisting}
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
147
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
148 型の注釈なしに関数を定義し, Haskell の対話環境である GHCi で型情報を取得してみる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
149 型情報を取得するには, :type の後ろに関数名を入力する(ソースコード\ref{src:type}).
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
150
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
151 \begin{lstlisting}[label=src:type, caption=型情報の取得]
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
152 *Jungle> :type getChildren
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
153 getChildren :: Node -> [Int] -> [Node]
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
154 \end{lstlisting}
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
155
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
156 そうすると, 推論された型情報 Node -$>$ [Int] -$>$ [Node]が得られる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
157 この型情報は期待する型の定義と一致する.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
158
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
159 この情報はgetChildrenに含まれるいくつかの関数の型を確認することで導き出すことができる(ソースコード\ref{src:type2}).
15
a551888363cb describe type
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
160
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
161 \begin{lstlisting}[label=src:type2, caption=getChildrenに含まれる関数の型]
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
162 getNode :: Node -> Path -> Node
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
163 elems :: Map k a -> [a]
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
164 children :: Node -> Map Int Node
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
165 \end{lstlisting}
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
166
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
167 例えば, getChildrenの引数である, node と path は getNode に渡されているため, getNode の型である Node 型と Path 型であることが分かる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
168 返り値となる型は, elemsの[a]となる. このaは, elemsが受け取るMapの2つ目の型と一致するため, childrenの返り値であるMap Int Node より, [Node]ということが分かる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
169
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
170 Haskell では, プログラマが型の宣言を行わずとも, 型を推論し型安全を保つ.
49
0a8d66c9ccd1 describe the impl
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
171 しかし, 明示的な型宣言は可読性の向上や問題の発見に役に立つため, トップレベルの関数には型を明記することが一般的である.
34
345eacdf29e4 add apendix
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
172
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
173 \clearpage
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
174 \section{モナド}
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
175 Haskell では, さまざまな目的にモナドを使う.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
176 I/O 処理を行うためには IO モナドを使う必要がある.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
177 プログラミングを行うにあたり, I/O 処理は欠かせないため, モナドの説明を行う.
34
345eacdf29e4 add apendix
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
178
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
179 モナドとは, 型クラスの 1 つである.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
180 型クラスは型の振る舞いを定義するものである.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
181 ある型クラスのインスタンスである型は, その型クラスに属する関数の集まりを実装する.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
182 これは, それらの関数がその型ではどのような意味になるのか定義するということである.
34
345eacdf29e4 add apendix
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
183
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
184 モナドとなる型は, 型変数として具体型をただ 1 つ取る.
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
185 これにより何かしらのコンテナに包まれた値を実現する.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
186 モナドの振る舞いは型クラスとして実装し, 関数として return および $>>$= (bind) を定義する(ソースコード\ref{monad}).
16
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
187
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
188 \begin{lstlisting}[label=monad, caption=モナドに属する関数の型]
16
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
189 return :: Monad m => a -> m a
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
190 (>>=) :: Monad m => m a -> (a -> m b) -> m b
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
191 \end{lstlisting}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
192
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
193 return は値を持ち上げてコンテナに包む機能を実装する(図\ref{fig:monad_return}).
16
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
194
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
195 \begin{figure}[!htbp]
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
196 \begin{center}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
197 \includegraphics[scale=0.6]{./images/monad_return.pdf}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
198 \end{center}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
199 \caption{モナドに属する return 関数}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
200 \label{fig:monad_return}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
201 \end{figure}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
202
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
203 bind は, 「コンテナに包まれた値」と, 「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり, コンテナに包まれた値をその関数に適用する(図\ref{fig:monad_bind}).
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
204 適用する際, 前のコンテナの結果に依存して, 後のコンテナの振る舞いを変えられる.
16
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
205
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
206 \begin{figure}[!htbp]
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
207 \begin{center}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
208 \includegraphics[scale=0.6]{./images/monad_bind.pdf}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
209 \end{center}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
210 \caption{モナドに属する $>$$>$= (bind) 関数}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
211 \label{fig:monad_bind}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
212 \end{figure}
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
213
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
214 この2つの関数を利用することにより, 文脈を保ったまま関数を繋いでいくことができる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
215 Haskell の遅延評価は記述した順序で実行することを保証しないが, モナドの bind は実行順序の指定も可能で, IO モナドを bind で繋いだものは記述順に実行することができる.
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
216
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
217 \subsubsection{Maybe モナド}
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
218
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
219 文脈を保ったまま関数を繋いでいくとはどういうことなのか, 具体例を用いて説明する.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
220
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
221 Maybe 型は失敗する可能性を扱うデータ型である(ソースコード\ref{src:maybe}).
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
222
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
223 \begin{lstlisting}[label=src:maybe,caption=Maybe型の定義]
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
224 data Maybe a = Nothing | Just a
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
225 \end{lstlisting}
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
226
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
227 失敗したことを表す Nothing, もしくは成功したことを表す Just a のいずれかの値を取る.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
228
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
229 Maybe 型が使われている例として, Data.Map の lookup 関数がある.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
230 Data.Map は Key と Value を保持する辞書型のデータ構造である.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
231 何らかの Key を渡して, Data.Map から値を取得しようとした時, 返される値は Maybe Value 型である.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
232 何かしらの値が取得できた場合は, Just a として Value に Just がついて返される.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
233 取得できなければ, Nothing が返る.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
234
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
235 Maybe モナドを使いたい場面は, 失敗するかもしれないという計算を繋いでいく時である.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
236 Maybe モナドの定義をみていく(ソースコード\ref{src:maybe_monad}).
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
237
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
238 \begin{lstlisting}[label=src:maybe_monad, caption=Maybeモナドの定義]
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
239 instance Monad Maybe where
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
240 return x = Just x
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
241 Nothing >>= f = Nothing
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
242 Just x >>= f = f x
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
243 \end{lstlisting}
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
244
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
245 instance Monad Maybe whereというのは, Maybe型をモナド型クラスのインスタンスとするのに使う構文である.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
246 モナド型クラスに属させるために必要な関数である return と $>>$= (bind) を, Maybeではどう振る舞うかを考え定義していく.
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
247
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
248 Maybe モナドの return は, 値をJustで包む.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
249 これがコンテナに包む機能という意味である.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
250
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
251 $>>$= (bind) は, 「コンテナに包まれた値」と, 「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり, コンテナに包まれた値をその関数に適用すると説明した.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
252 Maybe モナドの場合, コンテナが Nothing なら, そのまま Nothing を返す.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
253 コンテナがJustならば, Just に包まれた値を取り出し, 「普通の値を取りコンテナに包まれた値を返す関数」に適用する.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
254
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
255 失敗するかもしれない計算を繋いでいくとはどういうことなのか.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
256 単純な関数を定義して説明する(ソースコード\ref{src:updown}).
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
257
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
258 \begin{lstlisting}[label=src:updown, caption=up関数とdown関数]
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
259 up 4 = Nothing
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
260 up n = Just (n + 1)
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
261
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
262 down 0 = Nothing
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
263 down n = Just (n - 1)
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
264 \end{lstlisting}
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
265
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
266 関数 up と down を定義した.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
267 up の場合, 引数として4が渡された場合は上がれないため失敗,
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
268 down の場合, 引数として0が渡された場合は下がれないため失敗と考える.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
269
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
270 3 という値にdown, down, up, up 繰り返していく時, モナドを使わない場合ソースコード\ref{src:up_without_monad}のように定義することになる.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
271
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
272 \begin{lstlisting}[label=src:up_without_monad, caption=Maybeモナドを使わずにupとdownを行う]
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
273 updown :: Maybe Int
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
274 updown = case down 3 of
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
275 Nothing -> Nothing
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
276 Just place1 -> case down place1 of
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
277 Nothing -> Nothing
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
278 Just place2 -> case up place2 of
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
279 Nothing -> Nothing
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
280 Just place3 -> up place3
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
281
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
282 \end{lstlisting}
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
283
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
284 case 式は, caseとofの間の式を評価し, その値によって評価を分岐させるためのものである.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
285 case を受け取る $->$ の左の部分には式の値を書き, その式の値によって評価を分岐させる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
286 例えば, 3 行目は down 3 の結果が Nothing なら, Nothing を返すという意味である.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
287 Justの場合, 値をplace1という変数に束縛しその後の処理を続ける.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
288
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
289 ソースコード\ref{src:up_without_monad}では, 毎回失敗したか成功したか確認するために非常に煩雑なコードとなってしまった.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
290 これを文脈を保ったまま, 関数を繋げられるモナドを使えばソースコード\ref{src:upmonad}のように記述できる.
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
291
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
292 \begin{lstlisting}[label=src:upmonad, caption=Maybeモナドを用いてupとdownを行う]
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
293 return 3 >>= down >>= down >>= up >>= up
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
294 \end{lstlisting}
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
295
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
296 Maybe モナドを使うことで, この計算は失敗しているかもしれないという文脈を保ったまま処理を繋げていくことができる.
37
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
297
909c9097ebb8 describe the maybe monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
298 \subsubsection{IO モナド}
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
299 Haskellで副作用を持つ処理を実行するには, IO モナドを利用する.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
300 IO モナドは, 処理系が現実世界に対する副作用に変換できるモナドである.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
301
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
302 IO モナド自体は, 「文字を1文字取ってくる」といった命令書である.
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
303 bind を使って, 小さな命令書を合成して大きな命令書を作成できる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
304 最終的に, mainという名前をつけることで初めてランタイムにより実行される(ソースコード\ref{src:iomonad}).
16
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
305
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
306 \begin{lstlisting}[label=src:iomonad, caption=Hello Worldと出力]
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
307 main :: IO ()
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
308 main = putStrLn "Hello, World!"
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
309 \end{lstlisting}
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
310
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
311 Haskell の関数には副作用がないと述べたが, IO モナドを返す関数にも副作用は存在しない.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
312
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
313 例えば, Jungle には getRootNode というIOを返す関数がある.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
314 呼び出した状況によって, 返ってくるノードが違うため副作用があるようにみえる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
315 しかし, 実際にこの関数が返すのは, 「ノードを取得する」という命令書である.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
316 どんな状況においても同じ命令書を返すため, 副作用はない.
16
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
317
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
318 \clearpage
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
319 \section{遅延評価}
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
320 Haskell では, 必要となるまで式の評価が遅延される.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
321 Haskell の対話環境である GHCi でどのように評価されるか確認することができる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
322
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
323 GHCiで評価を強制せずに値を表示する :sprint コマンドを使う.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
324 例えば, x を定義した後に :sprint コマンドを使うとソースコード\ref{src:sprint} のように表示される\footnote{GHCiでは, 関数や変数を定義する際にはletが必要となる.}.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
325
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
326 \begin{lstlisting}[label=src:sprint, caption=sprintコマンドの使用例]
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
327 ghci> let x = 1 + 2
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
328 ghci> :sprint x
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
329 x = _
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
330 \end{lstlisting}
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
331
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
332 \_ は式が未評価であることを示している.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
333 Haskell ではこの未評価の部分を thunk と呼ぶ.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
334
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
335 \begin{lstlisting}[label=src:list_sprint, caption=リストの評価の様子]
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
336 ghci> let y = map (+1) [1,2,3] :: [Int]
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
337 ghci> :sprint y
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
338 y = _
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
339 ghci> length y
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
340 3
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
341 ghci> :sprint y
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
342 y = [_,_,_]
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
343 ghci> head y
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
344 2
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
345 ghci> :sprint y
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
346 y = [2,_,_]
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
347 \end{lstlisting}
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
348
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
349 リストを使ってどのように評価されるのか確認する.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
350 ソースコード\ref{src:list_sprint} では, まずmap関数を利用してリストの要素を全て (+1) している.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
351 しかし, この計算は必要となるまで計算されない.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
352 直後にsprintを行うと, ただ\_が表示される.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
353
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
354 リストの長さを表示する関数であるlengthを実行後に sprint を行った場合は,
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
355 リストの要素数を確認しているため、要素数分のthunkを持つリストとなる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
356
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
357 実際に値が必要となる関数を適用する.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
358 head はリストの先頭要素を取得する関数である.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
359 head を適用後に, sprint を行うと先頭要素だけが評価されたリストとなる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
360
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
361 リストの例より, Haskell では本当に値が必要となるまで決して計算しないことが分かる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
362
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
363 \subsubsection{引数のメモ化}
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
364
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
365 Haskell の遅延評価では引数のメモ化を行う.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
366 ある関数の仮引数が, その関数の本体に複数回出現したとしても評価回数が1回のみである.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
367 例えば, ソースコード\ref{memo} は, 図 \ref{fig:memo} のようにメモ化される.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
368 y は未評価のthunkとして同じ x を参照する.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
369 そのため, x が2回評価されることはない.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
370
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
371 \newpage
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
372 \begin{lstlisting}[label=memo, caption=メモ化]
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
373 Prelude> let x = 1 + 2 :: Int
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
374 Prelude> let y = (x,x)
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
375 Prelude> :sprint y
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
376 y = (_,_)
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
377 \end{lstlisting}
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
378
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
379 \begin{figure}[!htbp]
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
380 \begin{center}
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
381 \includegraphics[scale=0.6]{./images/memo.pdf}
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
382 \end{center}
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
383 \caption{メモ化の様子}
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
384 \label{fig:memo}
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
385 \end{figure}
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
386
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
387 \clearpage
5
658281be77ec describe the abstract
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
388 \section{並列実行}
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
389 Haskellはデフォルトではシングルスレッドで走る.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
390 並列に実行したい場合は, -threaded 付きでコンパイルし, RTS の -N オプションを付けて実行する.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
391 -N オプションで指定された数だけ, OSのスレッドが立ち上がり実行される(ソースコード\ref{concurrent}).
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
392
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
393 \begin{lstlisting}[language=bash, label=concurrent, caption=並列実行の様子]
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
394 $ ghc -O2 par.hs -threaded
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
395 $ ./par +RTS -N2
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
396 \end{lstlisting}
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
397
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
398 当然これだけでは並列に動かず, 並列に実行できるようにプログラムを書く必要がある.
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
399
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
400 Control.Parallel.Strategies モジュールにある,
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
401 Eval モナドを用いた並列化について説明する.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
402 Eval モナドは並列処理を行うためのモナドである. Eval モナドで並列処理を行う使用例を示す(ソースコード\ref{src:evalmonad}).
39
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
403
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
404 %% 完全に動くプログラム
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
405 \begin{lstlisting}[label=src:evalmonad, caption=Evalモナドの使用例]
39
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
406 import Control.Parallel.Strategies
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
407
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
408 main = print (runEval test)
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
409
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
410 num :: Integer
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
411 num = 1000000
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
412
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
413
39
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
414 test :: Eval (Integer, Integer)
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
415 test = rpar (sum' 0 num) >>= (\a ->
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
416 rpar (sum' num (num*2)) >>= (\b ->
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
417 return (a,b)))
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
418
39
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
419 sum' :: Integer -> Integer -> Integer
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
420 sum' begin end = if begin < end
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
421 then begin + (sum' (begin + 1) end)
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
422 else begin
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
423 \end{lstlisting}
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
424
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
425 まず, Eval モナドが定義された, Control.Parallel.Strategies をロードし, Eval モナドを利用できるようにしている.
39
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
426
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
427 Haskell のプログラムはmainという名前と実行したい関数を関連付けることで実行される.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
428 今回は, print (runEval test)が実行される.
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
429
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
430 並列処理を行いたい箇所には, rpar を使う.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
431 rpar の引数とした関数は並列に実行可能であることを示すことができる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
432 Eval モナドの関数の型をみると, rpar は, a を モナドに包み, 逆にrunEval はモナドから a を取り出している(ソースコード\ref{eval}).
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
433 rpar で並列化可能計算を示したあと, runEvalで実行するという流れになる.
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
434
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
435 \begin{lstlisting}[label=eval, caption=Eval モナドの型]
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
436 data Eval a
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
437 instance Monad Eval
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
438
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
439 runEval :: Eval a -> a
39
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
440 rpar :: a -> Eval a
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
441 \end{lstlisting}
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
442
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
443 rpar を利用している test 関数は rpar モナドをbindで接続しているが, 入れ子構造となり書き方は煩雑となっている.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
444 Haskell にはモナドのために do 構文というシンタックスシュガーが用意されており, それを用いることでソースコード\ref{src:do}のように書くことができる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
445 do 構文を使うことでbindの入れ子構造を簡潔に書ける.
39
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
446
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
447 \begin{lstlisting}[label=src:do, caption=do構文]
39
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
448 test :: Eval (Integer, Integer)
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
449 test = do
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
450 a <- rpar (sum' 0 num)
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
451 b <- rpar (sum' num (num*2))
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
452 return (a,b)
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
453 \end{lstlisting}
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
454
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
455 sum' は2つの引数をとって, 開始点から終了点までの値をすべて足し合わせる関数である.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
456 並列処理に負荷を与えるために使う.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
457 ifで, 開始点が終了点を超えてないか調べ, 超えてなければ再帰的に呼び出して足し合わせを行う.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
458
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
459 test で返ってくる型は, Eval (Integer, Integer)で, その後 runEval 関数を適用することで, (Integer, Integer)となる.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
460 そして最後にprint で出力される.
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
461
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
462 Haskell は遅延評価を行うため, 必要となるまで式の評価が遅延される.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
463 今回の場合, mainのprintがなければそもそも計算が行われない(ソースコード\ref{src:donteval}).
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
464
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
465 \begin{lstlisting}[label=src:donteval, caption=計算が行われない例]
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
466 main = return (runEval test)
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
467 \end{lstlisting}
39
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
468
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
469 出力することで, 値が必要となるため計算される.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
470 また, testで返される2つの計算を1つだけ出力するようにした場合, 1つのみ計算され並列実行は行われない(ソースコード\ref{src:donteval2}).
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
471 fst は, (a,b)とあったとき aを取得する関数である.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
472
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
473 \begin{lstlisting}[label=src:donteval2, caption=並列実行されない例]
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
474 main = print (fst (runEval test))
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
475 \end{lstlisting}
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
476
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
477 Haskell で並列実行を行いたい場合は, 遅延評価に気をつける必要がある.
48
88b11a3afb93 describe deos
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
478 rpar は単なるマーキングに過ぎず, rpar に渡したからといって直ちに並列実行が行われるわけではない.
60
79d168016df4 add memorize
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 49
diff changeset
479 rpar で作成した Eval モナドを runEval に渡したあと, 値が必要となるprintなどを行えば, 並列に実行可能な部分が並列に実行される.
39
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
480
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
481 また, rpar を使用する際, 別の計算の値に依存する計算がある場合, その2つの計算は並列実行できない.
49
0a8d66c9ccd1 describe the impl
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
482 例えば, ソースコード\ref{src:rpar}の場合は並列実行ができない.
16
eb6a70fc9c9f describe the haskell
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
483
47
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
484 \begin{lstlisting}[label=src:rpar, caption=前の計算に依存した計算]
39
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
485 test2 :: Eval (Integer, Integer)
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
486 test2 = do
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
487 a <- rpar (sum' 0 num)
a7981a22f12e describe the eval monad
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
488 b <- rpar (sum' num (if a < num then a else (num*2)))
9
70bda541eb1d add pdf
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
489 return (a,b)
8
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
490 \end{lstlisting}
a145ceb871d3 describe chapter 1
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
491