\chapter{Haskellとは} \label{ch:haskell}
Haskell とは純粋関数型プログラミング言語である。

\section{純粋関数型プログラミング}
関数とは、一つの引数を取り一つの結果を返す変換器のことである。
関数型プログラミング言語では、関数を引数に適用させていくことで計算を行う。

既存の手続き型言語と異なり、手順を記述するのではなく、この関数が何であるかということを記述する。
例えば、Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する。

\begin{lstlisting}[label=src:fib, caption=フィボナッチ数列]
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)
\end{lstlisting}

Haskell は、関数を引数を適用するという考えに基づいて、抽象的なプログラミングを可能とする。

純粋関数型プログラミングでは、変数の代入は一度のみで後から書き換えることはできない。
また、関数自体は副作用を持たない\footnote{副作用を実現するには、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 は、すべての式、すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる。

型検査でも捕まえられないエラーは存在する。
例えば、式 "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 で新しい型を宣言する一番簡単な方法は、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は値コンストラクタである。
値コンストラクタは大文字で始まる必要があり、複数の型に対して同じ名前の値コンストラクタを用いることはできない。

data キーワードによる型宣言では、値コンストラクタが引数を取ることもできる。
標準ライブラリにおける Maybe 型はソースコード\ref{maybe}のように定義されている。

\begin{lstlisting}[label=maybe, caption=Maybe型の定義]
data Maybe a = Nothing | Just a
\end{lstlisting}

Maybeは型引数を取るので、型コンストラクタと呼ばれる。
型コンストラクタは、型引数を受け取ってはじめて具体型を生成する。
単なる Maybe という型の値は存在できない。
Maybe Intや、Maybe Charといった形で存在することになる。
具体型を生成するため何かしらの型引数を渡す必要があるが、
殆どの場合、型コンストラクタに明示的に型引数を渡さなくても型推論があるので問題がない。

data キーワードによる型宣言では、再帰的に定義することもできる。
例えば木構造といったデータ型はソースコード\ref{tree}のように定義できる。

\begin{lstlisting}[label=tree, caption=再帰的なデータ型の定義]
data Tree a = EmptyTree | Node a (Tree a) (Tree a)
\end{lstlisting}

この型宣言は、「Tree a 型は、空の木、もしくは何らかの値 a と 2 つの木を含む要素である」ということを表している。

\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 の型クラスは、動的型付けの利点を安全で使いやすい形で実現するものである。

自作のデータ型を作成する際は、型クラスを利用することで、既存の 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) を定義する。

\begin{lstlisting}[label=monad, caption=モナドに属する関数]
return :: Monad m => a -> m a
(>>=) :: Monad m => m a -> (a -> m b) -> m b
\end{lstlisting}

return は値を持ち上げてコンテナに包む機能を実装する（図\ref{fig:monad_return}）。

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[scale=0.6]{./images/monad_return.pdf}
 \end{center}
 \caption{モナドに属する return 関数}
 \label{fig:monad_return}
\end{figure}

bind は、「コンテナに包まれた値」と、「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり、コンテナに包まれた値をその関数に適用する（図\ref{fig:monad_bind}）。
適用する際、前のコンテナの結果に依存して、後のコンテナの振る舞いを変えられる。

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[scale=0.6]{./images/monad_bind.pdf}
 \end{center}
 \caption{モナドに属する $>$$>$= (bind) 関数}
 \label{fig:monad_bind}
\end{figure}

この2つの関数を利用することにより、文脈を保ったまま関数を繋いでいくことができる。
Haskell の遅延評価は記述した順序で実行することを保証しないが、モナドの bind は実行順序の指定も可能で、IO モナドを bind で繋いだものは記述順に実行することができる。

Haskellで副作用を持つ処理を実行するには、IO モナドを利用する。
IO モナド自体は単なる命令書であり、命令ではない。
bind を使って、小さな命令書を合成して大きな命令書を作成できる。
最終的に、mainという名前をつけることで初めてランタイムにより実行される。

Haskell の関数には副作用がないと述べたが、IO モナドを返す関数にも副作用は存在しない。

例えば、getChar という関数がある。
呼び出した状況によって、返ってくる文字が違うため副作用があるようにみえる。
しかし、実際にこの関数が返すのは、「一文字読み込む」という命令書である。
どんな状況においても同じ命令書を返すため、副作用はない。

\clearpage
\section{並列実行}
Haskellはデフォルトではシングルスレッドで走る。
並列に実行したい場合は、-threaded 付きでコンパイルし、RTS の -N オプションを付けて実行する。
-N オプションで指定された数だけ、OSのスレッドが立ち上がり実行される。

\begin{lstlisting}[language=bash, label=concurrent, caption=並列実行の様子]
$ ghc -O2 par.hs -threaded
$ ./par +RTS -N2
\end{lstlisting}

当然これだけでは並列に動かず、並列に実行できるようにプログラムを書く必要がある。

Haskell は遅延評価を行うため、必要となるまで式の評価が遅延される。
普段は気にする必要はないが、並列実行ではどのように評価されるか意識する必要がある。
並列に動くように処理を分割したとしても、値が必要になるまで評価されない。
この問題は、Control.DeepSeq モジュールにある deepseq 関数を使用し、式を即時評価することで解決できる。

Haskellの並列化手法はいくつかあるが、その中で最もシンプルなのは Eval モナドを利用することである。
Control.Parallel.Strategies モジュールをインポートすることで使用できる。


\begin{lstlisting}[label=eval, caption=Eval モナド]
data Eval a
instance Monad Eval

runEval :: Eval a -> a

rpar :: a -> Eval a
rseq :: a -> Eval a
\end{lstlisting}

rpar は、引数が並列処理可能であることを示す。
rseq は、引数を評価し、結果を待つように示す。
どちらも式が完全に即時評価されるわけではないので、出力を挟んだり、deepseq 関数をうまく活用する必要がある。
runEval は、評価を実行し結果を返す操作である。
実際の利用方法として２つのパターンを紹介する。


\begin{lstlisting}[label=rpar/rpar, caption=rpar/rpar]
runEval $ do
   a <- rpar (f x)
   b <- rpar (f y)
   return (a,b)
\end{lstlisting}

rpar/rpar パターンは即座に return される（図\ref{fig:rpar}）。
単純に並列に動かしたい時に利用する。

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[scale=0.6]{./images/rpar_rpar.pdf}
 \end{center}
 \caption{rpar/rpar パターン}
 \label{fig:rpar}
\end{figure}

\begin{lstlisting}[label=rpar/rseq/rseq, caption=rpar/rseq/rseq]
runEval $ do
    a <- rpar (f x)
    b <- rseq (f y)
    rseq a
    return (a,b)
\end{lstlisting}

rpar/rseq/rseq パターンは、f x および f y の結果を待ってから return する（図\ref{fig:rseq}）。
他の処理が結果を必要としている時に利用する。

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[scale=0.6]{./images/rpar_rseq.pdf}
 \end{center}
 \caption{rpar/rseq/rseq パターン}
 \label{fig:rseq}
\end{figure}

rparは非常にコストが低いため、リストに対してmapするといった適用の仕方でも充分な並列性が出る。
そのための関数 parMap も、 Control.Parallel.Strategies モジュールには用意されている。