# HG changeset patch # User Daichi TOMA # Date 1391195753 -32400 # Node ID a551888363cb035dd95317452c3a25e1eb7cb988 # Parent 729ec8d5a16dd5017376dcaa232127c6d4b6850a describe type diff -r 729ec8d5a16d -r a551888363cb paper/abstract.tex --- a/paper/abstract.tex Fri Jan 31 04:04:44 2014 +0900 +++ b/paper/abstract.tex Sat Feb 01 04:15:53 2014 +0900 @@ -1,4 +1,5 @@ \begin{abstract} + Haskellは純粋関数型プログラミング言語である。 純粋であるため、引数が同じならば関数は必ず同じ値が返すことが保証されている。 純粋性は、関数の正しさを簡単に推測できる、関数同士を容易に組み合わせることができるといったメリットをもたらす。 diff -r 729ec8d5a16d -r a551888363cb paper/chapter1.tex --- a/paper/chapter1.tex Fri Jan 31 04:04:44 2014 +0900 +++ b/paper/chapter1.tex Sat Feb 01 04:15:53 2014 +0900 @@ -1,16 +1,27 @@ \chapter{Haskellとは} \label{ch:haskell} Haskell とは純粋関数型プログラミング言語である。 -Haskell では、変数の代入は一度のみで書き換えることはできない。 -また、引数が同じならば関数は必ず同じ値を返すことが保証されている。 -このような特徴から既存の手続き型言語と同じようにプログラムを書くことはできず、関数を組み合わせることでプログラミングを行う。 -\section{関数型プログラミング} +\section{純粋関数型プログラミング} 関数とは、一つの引数を取り一つの結果を返す変換器のことである。 -関数型プログラミング言語では、引数を関数に作用させていくことで計算を行う。 +関数型プログラミング言語では、関数に引数を作用させていくことで計算を行う。 + +既存の手続き型言語と異なり、手順を記述するのではなく、この関数が何であるかということを記述する。 +例えば、Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する。 -Haskell は純粋であり、引数が同じならば関数は必ず同じ値を返すことが保証されている。 -これはつまり、関数の正しさを簡単に推測でき、また関数同士を容易に組み合わせられることを意味している。 -実際、Haskell では小さな関数をつなぎ合わせることでプログラミングを行う。 +\begin{lstlisting}[label=src:fib, caption=フィボナッチ数列] +fib 0 = 0 +fib 1 = 1 +fib n = fib (n-2) + fib (n-1) +\end{lstlisting} + +Haskell は、関数に引数を適用するという考えに基づいて、抽象的なプログラミングを可能とする。 + +純粋関数型プログラミングでは、変数の代入は一度のみで後から書き換えることはできない。 +また、関数自体は副作用を持たない\footnote{副作用を実現するには、Haskell のアクションという仕組みを用いる}。 +関数にできることは、何かを計算してその結果を返すことだけである。 +そのため、引数が同じならば関数は必ず同じ値を返すことが保証されている。 +この性質は関数の理解を容易にし、プログラムの証明を可能にする。 +正しいと分かる単純な関数を組み合わせて、より複雑な正しい関数を組み立てていくのが関数型言語のプログラミングスタイルである。 関数型プログラミング言語は、関数を第一級オブジェクトとして扱うことができ、高階関数を定義することができる。 これは、引数として関数を取ったり返り値として関数を返すことができるということである。 @@ -27,53 +38,204 @@ 関数型プログラミング言語では、ループといった処理を行う場合再帰を用いる。 また、リストの畳み込み関数といった再帰を用いた関数が標準ライブラリで提供されている。 +関数型言語は手続き型言語と比較して、関数の利用に関する制約が少ない。 +Haskell では、関数を用いたプログラミングを簡潔かつ強力にするための機能を多く提供している。 +関数をリストなどのデータ構造の要素にしたり、 関数が引数として関数を取ったり、 +関数の返り値として関数を返したり、関数を自分自身を用いて定義したりできる。 + \section{型} -Haskell は静的型付け言語である。 -全ての型に起因するエラーはコンパイル時に捕捉される。 -コンパイル時に多くのエラーを見つけてくれるため、プログラマがプログラムの正しさを確認するのに役に立つ。 -また、Haskell は型を明示しなくても、処理系により自動的に型が推論される。 -型安全を保ちながら、ほとんどの部分で型宣言を省略することができる\footnote{明示的な型宣言は可読性の向上や問題の発見に役に立つため、トップレベルの関数には型を明記することが一般的である。}。 +Haskell では、すべての式、すべての関数に型がある。 +値の型は、その値が同じ型の別の値と何らかの性質を共有していることを示す。 +例えば、数値は加算できる、文字列は表示できるといった性質である。 + +型システムはプログラムに抽象をもたらす。 +抽象を導入することで、低水準の詳細を気にせずプログラミングが可能になる。 +例えば、値の型が文字列ならば、どのように実装されているかという細かいことは気にせず、 +その文字列が他の文字列と同じように振る舞うとみなすことができる。 + +GHCi\footnote{Haskellの対話環境}では、式の前に :type コマンドを付けることで、式の型を確認することができる。 + +\begin{lstlisting}[caption=型の確認] +ghci> :type True +True :: Bool +\end{lstlisting} + +\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} + +\subsubsection{リスト型} +リストは同じ型の要素の並びである。角括弧で包み、各要素はコンマで区切る。 +リストの長さに制限はない。空リストは[]で表す。 +Haskell は遅延評価を行うので無限リストを作成することもできる。 + +リストの例をソースコード\ref{src:list}に示す。 + +\newpage +\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{型の安全性} -\subsubsection{データ型} -Haskellの標準なデータ型には、Int 型や、Float 型、Bool 型、Char 型などが存在する。 -data キーワードを用いることで、自作のデータ型を作ることもできる。 -標準ライブラリにおける Bool 型は\ref{bool}のように定義されている。 +Haskell では、評価の際に型に起因するエラーが起きないことを保証している。 +引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない。 +Haskell は、すべての式、すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる。 + +型検査でも捕まえられないエラーは存在する。 +例えば、式 "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 は、多相型である。多相型についてはのちほど説明する。 + +型推論では、適用可能な最も広い型が選択されてしまうため、制限するには明示的に型宣言を行う。 +明示的な型宣言は可読性の向上や問題の発見に役に立つため、トップレベルの関数には型を明記することが一般的である。 + + +\subsubsection{多相型} +Haskell の型は多相的である。 +型変数を使い、型を抽象化できる。 +型変数は、型安全を保ちながら、関数を複数の型に対して動作するようにできる。 +Haskell の型の名前は全て大文字から始まるが、型変数は小文字から始まる。 +任意の型のリストを引数に取り、その型の先頭要素を返すという関数 head の型はソースコード\ref{type_variable}のように定義される。 + +\begin{lstlisting}[label=type_variable, caption=型変数] +head :: [a] -> a +\end{lstlisting} + +\subsubsection{多重定義型} +Haskell の (+) は、整数や浮動小数点数のどちらにも使える。 +これは型にクラス制約を含めることで実現している。 + +\begin{lstlisting}[label=type_class, caption=クラス制約] +ghci> :t (+) +(+) :: Num a => a -> a -> a +\end{lstlisting} + +=$>$ というシンボルの前にあるものがクラス制約である。 +これは、a が Num 型クラスのインスタンスでなければいけないということを意味する。 +Num 型クラスのインスタンスとなる型は数値型である。 + +型クラスは型の振る舞いを定義するものである。 +ある型クラスのインスタンスである型は、その型クラスに属する関数の集まりを実装する。 +これは、それらの関数がその型ではどのような意味になるのか定義するということである。 + +例えば、Eq 型クラスのインスタンスとなる型は等値性をテストできる。 +この型クラスに属させるためには、(==)と、(/=)の 2 つの関数を実装する。 + +Haskell の型クラスは、動的型付けの利点を安全で使いやすい形で実現するものである。 + +\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 \end{lstlisting} この型宣言は、「Bool 型は True または False の値を取り得る」ということを表している。 +型のために新しく定義された値、TrueやFalseは値コンストラクタである。 +値コンストラクタは大文字で始まる必要があり、複数の型に対して同じ名前の値コンストラクタを用いることはできない。 -\subsubsection{型変数} -Haskell の型は多相的である。 -型変数を使い、型を抽象化できる。 -型変数は、型安全を保ちながら、関数を複数の型に対して動作するようにできる。 -Haskell の型の名前は全て大文字から始まるが、型変数は小文字から始まる。 -任意の型のリストを引数に取り、その型の先頭要素を返すという関数 head の型は\ref{type_variable}のように定義される。 +data キーワードによる型宣言では、値コンストラクタが引数を取ることもできる。 +標準ライブラリにおける Maybe 型はソースコード\ref{maybe}のように定義されている。 -\begin{lstlisting}[label=type_variable, caption=型変数] -head :: [a] -> a +\begin{lstlisting}[label=maybe, caption=Maybe型の定義] +data Maybe a = Nothing | Just a \end{lstlisting} -データ型も型変数を使うことができる。例えばリストといったデータ型は、その要素の型を型変数として定義する。 -これらのデータ型は、型引数を受け取って具体型を生成する。 -言うまでもなく、型推論があるため明示的に型引数を渡す必要はない。 +Maybeは型引数を取るので、型コンストラクタと呼ばれる。 +型コンストラクタは、型引数を受け取ってはじめて具体型を生成する。 +単なる Maybe という型の値は存在できない。 +Maybe Intや、Maybe Charといった形で存在することになる。 +具体型を生成するため何かしらの型引数を渡す必要があるが、 +殆どの場合、型コンストラクタに明示的に型引数を渡さなくても型推論があるので問題がない。 -\subsubsection{型クラス} -型クラスは型の振る舞いを定義するものである。 -ある型クラスのインスタンスである型は、その型クラスに属する関数の集まりを実装する。 -ある型を型クラスのインスタンスにしようとする場合、それらの関数がその型ではどのような意味になるのか定義する。 -例えば、Eq 型クラスのインスタンスとなる型は等値性をテストできる。Show 型クラスのインスタンスとなる型は文字列として表現できる。 -いくつかの関数には型クラスが制約となるものがある。 -演算子 * の引数は、数を表す型クラスである Num 型クラスである必要がある。 +data キーワードによる型宣言では、再帰的に定義することもできる。 +例えば木構造といったデータ型はソースコード\ref{tree}のように定義できる。 -\begin{lstlisting}[label=multiply, caption=演算子 *] -(*) :: Num a => a -> a -> a +\begin{lstlisting}[label=tree, caption=再帰的なデータ型の定義] +data Tree a = EmptyTree | Node a (Tree a) (Tree a) \end{lstlisting} -1つの型はいくつもの型クラスのインスタンスとなることができる。 -自作のデータ型を作成する際に型クラスを利用することで、既存の Haskell ライブラリを利用できる。 +この型宣言は、「Tree a 型は、空の木、もしくは何らかの値 a と 2 つの木を含む要素である」ということを表している。 + +自作のデータ型を作成する際は、型クラスを利用することで、既存の Haskell ライブラリを利用できる。 +特定の型クラスは自動導出することも可能である。自動導出には deriving キーワードを使う。 +ソースコード\ref{deriving}は、Showのインスタンスを自動導出している。 + +\begin{lstlisting}[label=deriving, caption=型クラスの自動導出] +data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show) +\end{lstlisting} \section{モナド} Haskell では、さまざまな目的にモナドを使う。 diff -r 729ec8d5a16d -r a551888363cb paper/chapter4.tex --- a/paper/chapter4.tex Fri Jan 31 04:04:44 2014 +0900 +++ b/paper/chapter4.tex Sat Feb 01 04:15:53 2014 +0900 @@ -433,13 +433,13 @@ \begin{center} \begin{tabular}{|c||r|r|} \hline 測定 & Haskell & Java \\ \hline \hline - 読み込み & 28.33 s & 55.63 s \\ \hline + 読み込み & 28.33 s & 53.13 s \\ \hline 書き込み & 32.68 s & 76.4 s \\ \hline \end{tabular} \end{center} \end{table} -Haskell 版は、Java 版と比較して読み込みで 1.96 倍、書き込みで 2.3 倍の性能が出ている。 +Haskell 版は、Java 版と比較して読み込みで 1.87 倍、書き込みで 2.3 倍の性能が出ている。 書き込みが読み込みより性能差が出ている理由として遅延評価が考えられる。 Haskell では書き込みを行う際、完全に評価せず thunk として積み上げていく。 diff -r 729ec8d5a16d -r a551888363cb paper/master_paper.pdf Binary file paper/master_paper.pdf has changed