# HG changeset patch # User Daichi TOMA # Date 1391444823 -32400 # Node ID 909c9097ebb83e64d52adadfd299b2cc906c20a6 # Parent 8a998d8c391d509a15593f8dcc389369c0894d7f describe the maybe monad diff -r 8a998d8c391d -r 909c9097ebb8 paper/chapter1.tex --- a/paper/chapter1.tex Mon Feb 03 23:34:01 2014 +0900 +++ b/paper/chapter1.tex Tue Feb 04 01:27:03 2014 +0900 @@ -7,6 +7,7 @@ 既存の手続き型言語と異なり、手順を記述するのではなく、この関数が何であるかということを記述する。 例えば、Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する。 +Haskell は、関数を引数を適用するという考えに基づいて、抽象的なプログラミングを可能とする。 \begin{lstlisting}[label=src:fib, caption=フィボナッチ数列] fib :: Int -> Int @@ -15,242 +16,135 @@ fib n = fib (n-2) + fib (n-1) \end{lstlisting} -Haskell は、関数を引数を適用するという考えに基づいて、抽象的なプログラミングを可能とする。 +fib :: Int -$>$ Int は、関数の型宣言である。この-$>$は左結合である。 +この関数は、Int を受け取って Int を返す関数ということを示す。 +フィボナッチ数列の関数が三行に渡って書かれているが、これは Haskell のパターンマッチを活用している。 +引数が、0 ならば 2 行目の fib が呼び出される。 +引数が、1 ならば 3 行目の fib が呼び出される。 +上から順に引数と一致する行がないか調べていき、引数が 0 でも 1 でもなければ引数は n に束縛される。 + +フィボナッチ数列の関数は、自分自身を使って再帰的に定義している。 +再帰は、関数型プログラミング言語において必要不可欠な要素である。 +手続き型言語では、配列とループを主に用いてプログラミングを行うが、Haskell ではリスト構造と再帰を用いる。 純粋関数型プログラミングでは、変数の代入は一度のみで後から書き換えることはできない。 -また、関数自体は副作用を持たない\footnote{副作用を実現するには、Haskell のアクションという仕組みを用いる}。 -関数にできることは、何かを計算してその結果を返すことだけである。 -そのため、引数が同じならば関数は必ず同じ値を返すことが保証されている。 +フィボナッチ数列の関数でも、一度引数を束縛した n を書き換えることはできない。 + +関数にできることは、何かを計算してその結果を返すことだけであり、引数が同じならば関数は必ず同じ値を返すことが保証されている。 この性質は関数の理解を容易にし、プログラムの証明を可能にする。 正しいと分かる単純な関数を組み合わせて、より複雑な正しい関数を組み立てていくのが関数型言語のプログラミングスタイルである。 -関数型プログラミング言語は、関数を第一級オブジェクトとして扱うことができ、高階関数を定義することができる。 -これは、引数として関数を取ったり返り値として関数を返すことができるということである。 -高階関数は問題解決の強力な手段であり、関数型プログラミング言語にはなくてはならないものである。 -Haskell では標準ライブラリに、リストを処理するための便利な高階関数がいくつも定義されている。 +関数型プログラミング言語は、関数を変数の値にすることができる。 +つまりこれは、関数を第一級オブジェクトとして扱うことができるということである。 +Haskell は、引数として関数を取ったり返り値として関数を返すことができる高階関数を定義できる。 +高階関数の例として Haskell のカリー化が挙げられる。 Haskell では、全ての関数は一度に一つの引数だけを取る。 複数の引数を取るようにみえる関数は、実際には１つの引数を取り、その次の引数を受け取る関数を返す。 このように関数を返すことで全ての関数を一引数関数として表すことをカリー化という。 カリー化によって、関数を本来より少ない引数で呼び出した際に部分適用された関数を得ることができる。 -再帰もまた関数型プログラミング言語において必要不可欠な要素である。 -再帰とは、関数を関数自身を使って定義することをいう。 -関数型プログラミング言語では、ループといった処理を行う場合再帰を用いる。 -また、リストの畳み込み関数といった再帰を用いた関数が標準ライブラリで提供されている。 - -関数型言語は手続き型言語と比較して、関数の利用に関する制約が少ない。 -Haskell では、関数を用いたプログラミングを簡潔かつ強力にするための機能を多く提供している。 -関数をリストなどのデータ構造の要素にしたり、 関数が引数として関数を取ったり、 -関数の返り値として関数を返したり、関数を自分自身を用いて定義したりできる。 - -\clearpage \section{型} Haskell では、すべての式、すべての関数に型がある。 値の型は、その値が同じ型の別の値と何らかの性質を共有していることを示す。 例えば、数値は加算できる、文字列は表示できるといった性質である。 -型システムはプログラムに抽象をもたらす。 +型はプログラムに抽象をもたらす。 抽象を導入することで、低水準の詳細を気にせずプログラミングが可能になる。 例えば、値の型が文字列ならば、どのように実装されているかという細かいことは気にせず、 その文字列が他の文字列と同じように振る舞うとみなすことができる。 -GHCi\footnote{Haskellの対話環境}では、式の前に :type コマンドを付けることで、式の型を確認することができる。 - -\begin{lstlisting}[caption=型の確認] -ghci> :type True -True :: Bool -\end{lstlisting} - -Haskell は静的型検査によりエラーを広範囲に検出することができる。 -データ構造を独自の型で表現することができ、その定義したデータ構造も型検査でエラーがないか調べることができる。 - -\subsubsection{基本的な型} -Haskell は多くの基本型を提供している。 -Haskell の基本型を表\ref{tab:type}に示す。 -Haskell では、全ての型の名前は大文字で始まる。 - -\begin{table}[!htbp] -\caption{Haskellの基本的な型} -\label{tab:type} -\begin{center} -\begin{tabular}{|c||c|} \hline -型名 & 概要 \\ \hline \hline -Bool & 真理値 \\ \hline -Char & 文字 \\ \hline -String & 文字列 \\ \hline -Int & 固定精度整数 \\ \hline -Integer & 多倍長整数 \\ \hline -Float & 単精度浮動小数点数 \\ \hline -\end{tabular} -\end{center} -\end{table} - -\newpage -\subsubsection{リスト型} -リストは同じ型の要素の並びである。角括弧で包み、各要素はコンマで区切る。 -リストの長さに制限はない。空リストは[]で表す。 -Haskell は遅延評価を行うので無限リストを作成することもできる。 - -リストの例をソースコード\ref{src:list}に示す。 - -\begin{lstlisting}[label=src:list, caption=Haskellのリスト] -ghci> :type [True, False, False] -[True, False, False] :: [Bool] - -ghci> :type ['a','b','c','d'] -['a','b','c','d'] :: [Char] - -ghci> :type [[True, False], [False, True]] -[[True, False], [False, True]] :: [[Bool]] -\end{lstlisting} - -リストのリストを作ることもできる。 - -%\subsubsection{タプル型} -%タプルは固定サイズの要素の組である。各要素の型は異なってもよい。 -%各要素をコンマで区切って、全体を括弧で包む。 -% -%タプルの例をソースコード\ref{src:tuple}に示す。 -% -%\begin{lstlisting}[label=src:tuple, caption=Haskellのタプル] -%ghci> :type (False, True) -%(False, True) :: (Bool, Bool) -% -%ghci> :type ('a', True, False) -%('a', True, False) :: (Char, Bool, Bool) -% -%ghci> :type ([True, False], 'a', 'b') -%([True, False], 'a', 'b') :: ([Bool], Char, Char) -%\end{lstlisting} -% -\subsubsection{型の安全性} - +Haskell は静的型検査によりエラーを検出することができる。 Haskell では、評価の際に型に起因するエラーが起きないことを保証している。 引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない。 Haskell は、すべての式、すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる。 +エラーの検出の例として、Haskell で最もよく使われるデータ構造リストで確認を行う。 +また、リストの定義とあわせてデータ型の定義についても説明する。 + +リストとは、角括弧で包まれた同じ型の要素の並びである。[1,2,3] などと表現する。 +リストは以下のように定義されている。 + +\begin{lstlisting}[label=src:list, caption=Haskellのリスト定義] +data [] a = [] | a : [a] +\end{lstlisting} + +data というのは新しい型を定義する際に利用するキーワードである。 +[] というのが型名である。 + +型名の右に a というのがあるが、これは多相型を表すのに使う型変数である。 +リストは、Intのリスト、Floatのリストといった様々な型のリストを作ることができ、型変数を用いてそれを実現する。 +型変数が何の型になるのかという情報は実行時には決まっており、Haskell の型安全を保つ。 + += の右側が、新しい型の定義である。 +$|$ は、もしくはという意味である。 +つまりリストは、[] もしくは、a : [a] という値になることが分かる。 +[] は空リストを表す。型名と同じであるが、型とは名前領域が異なるため問題ない。 +型名はプログラム中では注釈としてしか使われないためである。 + +a : [a] は再帰的なデータ構造である。 +何らかの型の値 a を、: で繋げて、再度リストの定義を呼んでいる。 + +リストは無限に繋げることができ、リストの終端は空のリスト、つまり [] で終わる。 +[1,2,3]という様にリストを表すが、これは単なるシンタックスシュガーであり、 +内部では 1 : 2 : 3 : [] のように表現される。 + +リストは、: を使うことで新しい要素を加えることができるが、型変数は1つであり、全ての要素は同じ型の要素である必要がある。 +違った型の要素を付け加えようとすると Haskell はコンパイル時にエラーを出す。 +例えば、Int のリスト [3,4] に、文字である 'b' を付け加えようとした場合以下の様なエラーが発生する。 + +\begin{lstlisting}[label=src:list, caption=Haskellのコンパイル時エラー] +:3:7: + Couldn't match type `Int' with `Char' + Expected type: [Char] + Actual type: [Int] +\end{lstlisting} + 型検査でも捕まえられないエラーは存在する。 例えば、式 "1 `div` 0" は、型エラーではないが、0 での除算は定義されていないので評価時にエラーとなる。 + \subsubsection{型推論} Haskell は型推論を持つ。 型推論のない静的型付け言語は、プログラマが型の宣言を行うことが強制されるが Haskell では型の宣言は必須ではない。 -例として、型の宣言を省略し、引数を 2 倍にして返す関数を定義する。 - -\begin{lstlisting}[caption=doubleの宣言] -double x = x + x -\end{lstlisting} - -このとき、double の型は型推論され、次のように明示的に宣言したのと同じになる。 - -\begin{lstlisting}[caption=doubleの型推論] -double :: Num a => a -> a -double x = x + x -\end{lstlisting} - -この型の宣言は、「Num のインスタンスである a の型の値を引数にとり、a の型の値を返す」という意味である。 -a は、多相型である。多相型についてはのちほど説明する。 +例として、開発したデータベースで実装した関数に対して型推論を行ってみる。 +関数の詳細な動作はデータベースの実装で述べるが、getChildrenという、関数がある。 -型推論では、適用可能な最も広い型が選択されてしまうため、制限するには明示的に型宣言を行う。 -明示的な型宣言は可読性の向上や問題の発見に役に立つため、トップレベルの関数には型を明記することが一般的である。 - -\subsubsection{型の定義} -Haskell で新しい型を宣言する一番簡単な方法は、type キーワードを使って既存の型に別名を付けることである。 - -基本型で説明した、String 型は、文字のリスト[Char]の別名である。 -標準ライブラリでは、ソースコード\ref{string}のように定義されている。 - -\begin{lstlisting}[label=string, caption=String型の定義] -type String = [Char] -\end{lstlisting} - -完全に新しい型を宣言するには、data キーワードを用いる。 -標準ライブラリにおける Bool 型はソースコード\ref{bool}のように定義されている。 - -\begin{lstlisting}[label=bool, caption=Bool型の定義] -data Bool = False | True +\begin{lstlisting}[caption=getChildren関数] +getChildren node path = elems map + where + target = getNode node path + map = children target \end{lstlisting} -この型宣言は、「Bool 型は True または False の値を取り得る」ということを表している。 -型のために新しく定義された値、TrueやFalseは値コンストラクタである。 -値コンストラクタは大文字で始まる必要があり、複数の型に対して同じ名前の値コンストラクタを用いることはできない。 - -data キーワードによる型宣言では、値コンストラクタが引数を取ることもできる。 -標準ライブラリにおける Maybe 型はソースコード\ref{maybe}のように定義されている。 - -\begin{lstlisting}[label=maybe, caption=Maybe型の定義] -data Maybe a = Nothing | Just a -\end{lstlisting} +型の注釈なしに関数を定義し、Haskell の対話環境である GHCi で型情報を取得してみる。 +型情報を取得するには、:type の後ろに関数名を入力する。 -Maybeは型引数を取るので、型コンストラクタと呼ばれる。 -型コンストラクタは、型引数を受け取ってはじめて具体型を生成する。 -単なる Maybe という型の値は存在できない。 -Maybe Intや、Maybe Charといった形で存在することになる。 -具体型を生成するため何かしらの型引数を渡す必要があるが、 -殆どの場合、型コンストラクタに明示的に型引数を渡さなくても型推論があるので問題がない。 - -data キーワードによる型宣言では、再帰的に定義することもできる。 -例えば木構造といったデータ型はソースコード\ref{tree}のように定義できる。 - -\begin{lstlisting}[label=tree, caption=再帰的なデータ型の定義] -data Tree a = EmptyTree | Node a (Tree a) (Tree a) +\begin{lstlisting}[caption=型情報の取得] +*Jungle> :type getChildren +getChildren :: Node -> [Int] -> [Node] \end{lstlisting} -この型宣言は、「Tree a 型は、空の木、もしくは何らかの値 a と 2 つの木を含む要素である」ということを表している。 +そうすると、推論された型情報 Node -$>$ [Int] -$>$ [Node]が得られる。 +この型情報は期待する型の定義と一致する。 +Haskell では、プログラマが型の宣言を行わずとも、型を推論し型安全を保つ。 -\subsubsection{多相型} -Haskell の型は多相的である。 -型変数を使い、型を抽象化できる。 -型変数は、型安全を保ちながら、関数を複数の型に対して動作するようにできる。 -Haskell の型の名前は全て大文字から始まるが、型変数は小文字から始まる。 -任意の型のリストを引数に取り、その型の先頭要素を返すという関数 head の型はソースコード\ref{type_variable}のように定義される。 - -\begin{lstlisting}[label=type_variable, caption=型変数] -head :: [a] -> a -\end{lstlisting} +しかしながら、明示的な型宣言は可読性の向上や問題の発見に役に立つため、トップレベルの関数には型を明記することが一般的である。 -\subsubsection{多重定義型} -Haskell の (+) は、整数や浮動小数点数のどちらにも使える。 -これは型にクラス制約を含めることで実現している。 +\section{モナド} +Haskell では、さまざまな目的にモナドを使う。 +I/O 処理を行うためには IO モナドを使う必要がある。 +プログラミングを行うにあたり、I/O 処理は欠かせないため、モナドの説明を行う。 -\begin{lstlisting}[label=type_class, caption=クラス制約] -ghci> :t (+) -(+) :: Num a => a -> a -> a -\end{lstlisting} - -=$>$ というシンボルの前にあるものがクラス制約である。 -これは、a が Num 型クラスのインスタンスでなければいけないということを意味する。 -Num 型クラスのインスタンスとなる型は数値型である。 - +モナドとは、型クラスの 1 つである。 型クラスは型の振る舞いを定義するものである。 ある型クラスのインスタンスである型は、その型クラスに属する関数の集まりを実装する。 これは、それらの関数がその型ではどのような意味になるのか定義するということである。 -例えば、Eq 型クラスのインスタンスとなる型は等値性をテストできる。 -この型クラスに属させるためには、(==)と、(/=)の 2 つの関数を実装する。 - -Haskell の型クラスは、動的型付けの利点を安全で使いやすい形で実現するものである。 - -自作のデータ型を作成する際は、型クラスを利用することで、既存の Haskell ライブラリを利用できる。 -特定の型クラスは自動導出することも可能である。自動導出には deriving キーワードを使う。 -ソースコード\ref{deriving}は、Showのインスタンスを自動導出している。 - -\begin{lstlisting}[label=deriving, caption=型クラスの自動導出] -data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show) -\end{lstlisting} - -\clearpage -\section{モナド} -Haskell では、さまざまな目的にモナドを使う。 -I/O 処理を行うためには IO モナドを使う必要がある。 -プログラミングを行うにあたり、I/O 処理は欠かせないため、Haskell を利用するにあたってモナドの理解は必須である。 - -モナドとは、型クラスの 1 つである。 モナドとなる型は、型変数として具体型をただ１つ取る。 これにより何かしらのコンテナに包まれた値を実現する。 -モナドの振る舞いは型クラスとして実装し、関数として return および $>$$>$= (bind) を定義する。 +モナドの振る舞いは型クラスとして実装し、関数として return および $>>$= (bind) を定義する。 \begin{lstlisting}[label=monad, caption=モナドに属する関数] return :: Monad m => a -> m a @@ -281,6 +175,82 @@ この2つの関数を利用することにより、文脈を保ったまま関数を繋いでいくことができる。 Haskell の遅延評価は記述した順序で実行することを保証しないが、モナドの bind は実行順序の指定も可能で、IO モナドを bind で繋いだものは記述順に実行することができる。 +\subsubsection{Maybe モナド} + +文脈を保ったまま関数を繋いでいくとはどういうことなのか、具体例を用いて説明する。 + +Maybe 型は失敗する可能性を扱うデータ型である。 + +\begin{lstlisting}[ caption=Maybe型の定義] +data Maybe a = Nothing | Just a +\end{lstlisting} + +失敗したことを表す Nothing、もしくは成功したことを表す Just a のいずれかの値を取る。 +Maybe 型が使われている例として、Data.Map の lookup 関数がある。 +Data.Map は Key と Value を保持する辞書型のデータ構造である。 +何らかの Key を渡して、Data.Map から値を取得しようとした時、返される値は Maybe 型である。 +何かしらの値が取得できた場合は、Just a として値に Just がついて返される。 +取得できなければ、Nothing が返る。 + +Maybe モナドを使いたい場面は、失敗するかもしれないという計算を繋いでいく時である。 +Maybe モナドの定義をみていく。 + +\begin{lstlisting}[caption=Maybeモナドの定義] +instance Monad Maybe where + return x = Just x + Nothing >>= f = Nothing + Just x >>= f = f x +\end{lstlisting} + +Maybe モナドの return は、値をJustで包む。 +これがコンテナに包む機能という意味である。 +$>>$= (bind) は、「コンテナに包まれた値」と、「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり、コンテナに包まれた値をその関数に適用すると説明した。 +Maybe モナドの場合、コンテナが Nothing なら、そのまま Nothing を返す。 +コンテナがJustならば、Just に包まれた値を取り出し、「普通の値を取りコンテナに包まれた値を返す関数」に適用する。 + +失敗するかもしれない計算を繋いでいくとはどういうことなのか。 +単純な関数を定義して更に説明していく。 + +\begin{lstlisting}[caption=up, down関数] +up 4 = Nothing +up n = Just (n + 1) + +down 0 = Nothing +down n = Just (n - 1) +\end{lstlisting} + +関数 up と down を定義した。 +4以上はこれ以上、上がれないため失敗、 +0以下はこれ以上、下がれないため失敗と考える。 + +3 という値にdown, down, up、up 繰り返していく時、モナドを使わない場合以下のように定義することになる。 +case 式は、caseとofの間の式を評価し、その値によっ評価を分岐させることができる。 +case を受け取る $->$ の左の部分はパターンマッチを行うこともできる。 +また、case は式のため、$->$ の右の部分の全ての型は一意である必要がある。 +Haskell では分岐によって返ってくる値の型が異なるということはできない。 + +\begin{lstlisting}[caption=Maybe モナドを使わずにup, downを行う] +updown :: Maybe Int +updown = case down 3 of + Nothing -> Nothing + Just place1 -> case down place1 of + Nothing -> Nothing + Just place2 -> case up place2 of + Nothing -> Nothing + Just place3 -> up place3 + +\end{lstlisting} + +毎回、失敗したか成功したか確認するために非常に煩雑なコードとなってしまった。 +これを文脈を保ったまま、関数を繋げられる モナドを使えば以下のように記述できる。 + +\begin{lstlisting}[caption=Maybe モナドを用いてup, downを行う] +return 3 >>= down >>= down >>= up >>= up +\end{lstlisting} + +Maybe モナドを使うことで、この計算は失敗しているかもしれないという文脈を扱うことができる。 + +\subsubsection{IO モナド} Haskellで副作用を持つ処理を実行するには、IO モナドを利用する。 IO モナド自体は単なる命令書であり、命令ではない。 bind を使って、小さな命令書を合成して大きな命令書を作成できる。 diff -r 8a998d8c391d -r 909c9097ebb8 paper/introduciton.tex --- a/paper/introduciton.tex Mon Feb 03 23:34:01 2014 +0900 +++ b/paper/introduciton.tex Tue Feb 04 01:27:03 2014 +0900 @@ -2,7 +2,7 @@ \pagenumbering{arabic} Web サービスの脆弱性狙った攻撃が頻繁に発生している。 -脆弱性を悪用されると、Web サービス運営者は賠償など多大な損害を受ける。 +脆弱性を悪用されると、Web サービス運営者は賠償など多大な損害を受ける可能性がある。 純粋型プログラミング言語 Haskell は、バッファオーバーフローや、クロスサイトスクリプティング、SQL インジェクションを事前の型検査で防ぐことができる。 つまり、Haskell を用いることで信頼性の高い Web サービスを開発できると言える。 diff -r 8a998d8c391d -r 909c9097ebb8 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed