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

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

\subsubsection{関数の定義}
既存の手続き型言語と異なり, 手順を記述するのではなく, この関数が何であるかということを記述する. 
例えば, Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する. 
Haskell は, 関数を引数を適用するという考えに基づいて, 抽象的なプログラミングを可能とする. 

\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}

fib :: Int -$>$ Int は, 関数の型宣言である.
この関数は, Int を受け取って Int を返す関数ということを示す. 
フィボナッチ数列の関数が三行に渡って書かれているが, これは Haskell のパターンマッチを活用している. 
引数の値が 0 ならば 2 行目が呼び出され, 関数の結果は 0 となる.
引数の値が 1 ならば 3 行目が呼び出され, 関数の結果は 1 となる.
上から順に引数と一致する行がないか調べていき, 引数が 0 でも 1 でもなければ引数は n に束縛され, fib (n-2) + fib (n-1) が計算される.

フィボナッチ数列の関数は, 自分自身を使って再帰的に定義している. 
再帰は, 関数型プログラミング言語において必要不可欠な要素である. 
手続き型言語では, 配列とループを主に用いてプログラミングを行うが Haskell ではリスト構造と再帰を用いる. 

\subsubsection{変数の代入}
純粋関数型プログラミングでは, 変数の代入は一度のみで後から書き換えることはできない. 
フィボナッチ数列の関数でも, 一度引数を束縛した n を書き換えることはできない. 
関数にできることは, 何かを計算してその結果を返すことだけであり, 引数が同じならば関数は必ず同じ値を返すことが保証されている. 
この性質は関数の理解を容易にし, プログラムの証明を可能にする. 
正しいと分かる単純な関数を組み合わせて, より複雑な正しい関数を組み立てていくのが関数型言語のプログラミングスタイルである. 

\subsubsection{高階関数}
関数型プログラミング言語は, 関数を変数の値にすることができる. 
これは, 関数を第一級オブジェクトとして扱うことができるということである. 
Haskell は, 引数として関数を取ったり返り値として関数を返すことができる高階関数を定義できる. 

高階関数の例として Haskell のカリー化が挙げられる. 
Haskell では, 全ての関数は一度に一つの引数だけを取る. 
2 つのInt を受け取り, 大きい方を返す max の型はソースコード\ref{src:max}のように定義できる.

\begin{lstlisting}[label=src:max, caption=max関数]
max :: Int -> Int -> Int
max x y = if x <= y
            then y
            else x
\end{lstlisting}

この関数定義に現れる-$>$は左結合である. 
複数の引数を取るようにみえる関数は, 実際には１つの引数を取り, その次の引数を受け取る関数を返す（ソースコード\ref{src:max_curry}）.

\begin{lstlisting}[label=src:max_curry, caption=max関数のカリー化]
max :: Int -> (Int -> Int)
\end{lstlisting}

このように関数を返すことで全ての関数を一引数関数として表すことをカリー化という. 
カリー化によって, 関数を本来より少ない引数で呼び出した際に部分適用された関数を得ることができる（ソースコード\ref{src:partial}）.

\begin{lstlisting}[label=src:partial, caption=関数の部分適用]
x = max 3 -- x は Int -> Int の関数
x 4 -- (max 3) 4 の結果として 4 が返される
\end{lstlisting}

\clearpage
\section{型}
Haskell では, すべての式, すべての関数に型がある. 
値の型は, その値が同じ型の別の値と何らかの性質を共有していることを示す. 
例えば, 数値は加算できる, 文字列は表示できるといった性質である. 

型はプログラムに抽象をもたらす. 
型を導入することで, 低水準の詳細を気にせずプログラミングが可能になる. 
例えば, 値の型が文字列ならば, どのように実装されているかということを気にせず, 
その文字列が他の文字列と同じように振る舞うとみなすことができる. 

\subsubsection{型の定義と型検査}
Haskell は静的型検査によりエラーを検出することができる. 
Haskell では, 評価の際に型に起因するエラーが起きないことを保証している. 
例えば, 引数として整数を受け取る関数に文字列を渡そうとしても Haskell のコンパイラはこれを受け付けない. 
Haskell は, すべての式, すべての関数に型があるためコンパイル時に多くのエラーを捕まえることができる. 

エラーの検出の例として Haskell で最もよく使われるデータ構造であるリスト型で確認を行う. 
また, リスト型の定義とあわせてデータ型の定義についても説明する. 

リストとは, 角括弧で包まれた同じ型の要素の並びである. [1,2,3] などと表現する. 
リストはソースコード\ref{src:list}のように定義されている. 

\begin{lstlisting}[label=src:list, caption=Haskellのリスト定義]
data [] a = [] | a : [a]
\end{lstlisting}

data というのは新しい型を定義する際に利用するキーワードである. 
data キーワードのすぐ後にある [] a というのが型名である. 

a というのは, 型変数と呼ばれるものである.
型変数は任意の型を取ることができる.
リスト型は, Intのリスト, Floatのリストといった様々な型のリストを作ることができ, 型変数を用いてそれを実現する. 
型変数が何の型になるのかという情報は実行時には決まっており, 関数に渡される際に型の不整合が起きることはない.

= の右側には, 新しい型の定義として型の値となるものを列挙する.
$|$ は, もしくはという意味である. 
つまりリストは, [] もしくは a : [a] という値になることが分かる. 

[] は空リストを表す. 型名と同じであるが, 型とは名前領域が異なるため問題ない. 
型名はプログラム中では注釈としてしか使われないためである. 

a : [a] は再帰的なデータ構造である. 
値 a を : で繋げて, 再度リストの定義を呼んでいる. 

この定義 [] $|$ a : [a] は,  a : a : a : .. : a : [] となり, a が任意個続いた後に, [] が来ることとなる.
つまり, リストは無限に繋げることができ, リストの終端は空のリスト, つまり [] で終わる. 

Haskell では, [1,2,3] という様にリストを表すが, これは単なるシンタックスシュガーであり, 
内部では 1 : 2 : 3 : [] のように表現される. 

このように定義した型であっても, Haskell は型検査を行う.
リストは : を使うことで新しい要素を加えることができるが, 全ての要素は同じ型の要素である必要がある. 
違った型の要素を付け加えようとすると Haskell はコンパイル時にエラーを出す. 
例えば, Int のリスト [3,4] に, 文字である 'b' を付け加えようとした場合エラーが発生する（ソースコード\ref{src:error}）. 
型の定義に型変数を用いても Haskell は, [3,4] が何の型になるのかといった情報を推論する.
そのため文字である 'b' をIntのリスト [3,4] に付け加えることはできない.

\begin{lstlisting}[label=src:error, caption=Haskellのコンパイル時エラー]
<interactive>:3:7:
    Couldn't match type `Int' with `Char'
    Expected type: [Char]
      Actual type: [Int]
\end{lstlisting}

型検査でも捕まえられないエラーは存在する. 
例えば, 式 "1 `div` 0" は, 型エラーではないが, 0 での除算は定義されていないので評価時にエラーとなる. 

\subsubsection{型推論}
Haskell は型推論を持つ. 
型推論とは, 型の宣言をせずともそれを導くのに使われた関数の型シグネチャなどから自動的に型を決定する機構のことである. 
型推論のない静的型付け言語は, プログラマが型の宣言を行うことが強制されるが Haskell では型の宣言は必須ではない. 

例として, 開発したデータベースで実装した getChildren という関数に対して型推論を行ってみる（ソースコード\ref{src:getchildren}）. 

\begin{lstlisting}[label=src:getchildren, caption=getChildren関数]
getChildren node path = elems (children (getNode node path))
\end{lstlisting}

型の注釈なしに関数を定義し, Haskell の対話環境である GHCi で型情報を取得してみる. 
型情報を取得するには, :type の後ろに関数名を入力する（ソースコード\ref{src:type}）. 

\begin{lstlisting}[label=src:type, caption=型情報の取得]
*Jungle> :type getChildren
getChildren :: Node -> [Int] -> [Node]
\end{lstlisting}

そうすると, 推論された型情報 Node -$>$ [Int] -$>$ [Node]が得られる. 
この型情報は期待する型の定義と一致する. 

この情報はgetChildrenに含まれるいくつかの関数の型を確認することで導き出すことができる（ソースコード\ref{src:type2}）.

\begin{lstlisting}[label=src:type2, caption=getChildrenに含まれる関数の型]
getNode :: Node -> Path -> Node
elems :: Map k a -> [a]
children :: Node -> Map Int Node
\end{lstlisting}

例えば, getChildrenの引数である, node と path は getNode に渡されているため, getNode の型である Node 型と Path 型であることが分かる. 
返り値となる型は, elemsの[a]となる.  このaは, elemsが受け取るMapの2つ目の型と一致するため, childrenの返り値であるMap Int Node より, [Node]ということが分かる. 

Haskell では, プログラマが型の宣言を行わずとも, 型を推論し型安全を保つ. 
しかし, 明示的な型宣言は可読性の向上や問題の発見に役に立つため, トップレベルの関数には型を明記することが一般的である. 

\clearpage
\section{モナド}
Haskell では, さまざまな目的にモナドを使う. 
I/O 処理を行うためには IO モナドを使う必要がある. 
プログラミングを行うにあたり, I/O 処理は欠かせないため, モナドの説明を行う. 

モナドとは, 型クラスの 1 つである. 
型クラスは型の振る舞いを定義するものである. 
ある型クラスのインスタンスである型は, その型クラスに属する関数の集まりを実装する. 
これは, それらの関数がその型ではどのような意味になるのか定義するということである. 

モナドとなる型は, 型変数として具体型をただ 1 つ取る. 
これにより何かしらのコンテナに包まれた値を実現する. 
モナドの振る舞いは型クラスとして実装し, 関数として return および $>>$= (bind) を定義する（ソースコード\ref{monad}）. 

\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 で繋いだものは記述順に実行することができる. 

\subsubsection{Maybe モナド}

文脈を保ったまま関数を繋いでいくとはどういうことなのか, 具体例を用いて説明する. 

Maybe 型は失敗する可能性を扱うデータ型である（ソースコード\ref{src:maybe}）. 

\begin{lstlisting}[label=src:maybe,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 Value 型である. 
何かしらの値が取得できた場合は, Just a として Value に Just がついて返される. 
取得できなければ, Nothing が返る. 

Maybe モナドを使いたい場面は, 失敗するかもしれないという計算を繋いでいく時である. 
Maybe モナドの定義をみていく（ソースコード\ref{src:maybe_monad}）. 

\begin{lstlisting}[label=src:maybe_monad, caption=Maybeモナドの定義]
instance Monad Maybe where
    return x = Just x
    Nothing >>= f = Nothing
    Just x >>= f  = f x
\end{lstlisting}

instance Monad Maybe whereというのは, Maybe型をモナド型クラスのインスタンスとするのに使う構文である.
モナド型クラスに属させるために必要な関数である return と $>>$= (bind) を, Maybeではどう振る舞うかを考え定義していく. 

Maybe モナドの return は, 値をJustで包む. 
これがコンテナに包む機能という意味である. 

$>>$= (bind) は, 「コンテナに包まれた値」と, 「普通の値を取りコンテナに包まれた値を返す関数」を引数にとり, コンテナに包まれた値をその関数に適用すると説明した. 
Maybe モナドの場合, コンテナが Nothing なら, そのまま Nothing を返す. 
コンテナがJustならば, Just に包まれた値を取り出し, 「普通の値を取りコンテナに包まれた値を返す関数」に適用する. 

失敗するかもしれない計算を繋いでいくとはどういうことなのか. 
単純な関数を定義して説明する（ソースコード\ref{src:updown}）. 

\begin{lstlisting}[label=src:updown, caption=up関数とdown関数]
up 4 = Nothing
up n = Just (n + 1)

down 0 = Nothing 
down n = Just (n - 1)
\end{lstlisting}

関数 up と down を定義した. 
up の場合, 引数として4が渡された場合は上がれないため失敗, 
down の場合, 引数として0が渡された場合は下がれないため失敗と考える. 

3 という値にdown, down, up, up 繰り返していく時, モナドを使わない場合ソースコード\ref{src:up_without_monad}のように定義することになる. 

\begin{lstlisting}[label=src:up_without_monad, 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}

case 式は, caseとofの間の式を評価し, その値によって評価を分岐させるためのものである.
case を受け取る $->$ の左の部分には式の値を書き, その式の値によって評価を分岐させる.
例えば, 3 行目は down 3 の結果が Nothing なら, Nothing を返すという意味である.
Justの場合, 値をplace1という変数に束縛しその後の処理を続ける.

ソースコード\ref{src:up_without_monad}では, 毎回失敗したか成功したか確認するために非常に煩雑なコードとなってしまった. 
これを文脈を保ったまま, 関数を繋げられるモナドを使えばソースコード\ref{src:upmonad}のように記述できる. 

\begin{lstlisting}[label=src:upmonad, caption=Maybeモナドを用いてupとdownを行う]
return 3 >>= down >>= down >>= up >>= up
\end{lstlisting}

Maybe モナドを使うことで, この計算は失敗しているかもしれないという文脈を保ったまま処理を繋げていくことができる. 

\subsubsection{IO モナド}
Haskellで副作用を持つ処理を実行するには, IO モナドを利用する. 
IO モナドは, 処理系が現実世界に対する副作用に変換できるモナドである.

IO モナド自体は, 「文字を1文字取ってくる」といった命令書である.
bind を使って, 小さな命令書を合成して大きな命令書を作成できる. 
最終的に, mainという名前をつけることで初めてランタイムにより実行される（ソースコード\ref{src:iomonad}）. 

\begin{lstlisting}[label=src:iomonad, caption=Hello Worldと出力]
main :: IO ()
main = putStrLn "Hello, World!"
\end{lstlisting}

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

例えば, Jungle には getRootNode というIOを返す関数がある. 
呼び出した状況によって, 返ってくるノードが違うため副作用があるようにみえる. 
しかし, 実際にこの関数が返すのは, 「ノードを取得する」という命令書である. 
どんな状況においても同じ命令書を返すため, 副作用はない. 

\clearpage
\section{遅延評価}
Haskell では, 必要となるまで式の評価が遅延される.
Haskell の対話環境である GHCi でどのように評価されるか確認することができる.

GHCiで評価を強制せずに値を表示する :sprint コマンドを使う.
例えば, x を定義した後に :sprint コマンドを使うとソースコード\ref{src:sprint} のように表示される\footnote{GHCiでは, 関数や変数を定義する際にはletが必要となる.}.

\begin{lstlisting}[label=src:sprint, caption=sprintコマンドの使用例]
ghci> let x = 1 + 2
ghci> :sprint x
x = _
\end{lstlisting}

\_ は式が未評価であることを示している.
Haskell ではこの未評価の部分を thunk と呼ぶ.

\begin{lstlisting}[label=src:list_sprint, caption=リストの評価の様子]
ghci> let y = map (+1) [1,2,3] :: [Int]
ghci> :sprint y
y = _
ghci> length y
3
ghci> :sprint y
y = [_,_,_]
ghci> head y
2
ghci> :sprint y
y = [2,_,_]
\end{lstlisting}

リストを使ってどのように評価されるのか確認する.
ソースコード\ref{src:list_sprint} では, まずmap関数を利用してリストの要素を全て (+1) している.
しかし, この計算は必要となるまで計算されない.
直後にsprintを行うと, ただ\_が表示される.

リストの長さを表示する関数であるlengthを実行後に sprint を行った場合は, 
リストの要素数を確認しているため、要素数分のthunkを持つリストとなる.

実際に値が必要となる関数を適用する.
head はリストの先頭要素を取得する関数である.
head を適用後に, sprint を行うと先頭要素だけが評価されたリストとなる.

リストの例より, Haskell では本当に値が必要となるまで決して計算しないことが分かる.

\subsubsection{引数のメモ化}

Haskell の遅延評価では引数のメモ化を行う.
ある関数の仮引数が, その関数の本体に複数回出現したとしても評価回数が1回のみである.
例えば, ソースコード\ref{memo} は, 図 \ref{fig:memo} のようにメモ化される.
y は未評価のthunkとして同じ x を参照する.
そのため, x が2回評価されることはない.

\newpage
\begin{lstlisting}[label=memo, caption=メモ化]
Prelude> let x = 1 + 2 :: Int
Prelude> let y = (x,x)
Prelude> :sprint y
y = (_,_)
\end{lstlisting}

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[scale=0.6]{./images/memo.pdf}
 \end{center}
 \caption{メモ化の様子}
 \label{fig:memo}
\end{figure}

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

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

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

Control.Parallel.Strategies モジュールにある, 
Eval モナドを用いた並列化について説明する. 
Eval モナドは並列処理を行うためのモナドである. Eval モナドで並列処理を行う使用例を示す（ソースコード\ref{src:evalmonad}）. 

%% 完全に動くプログラム
\begin{lstlisting}[label=src:evalmonad, caption=Evalモナドの使用例]
import Control.Parallel.Strategies

main = print (runEval test) 

num :: Integer
num = 1000000


test :: Eval (Integer, Integer)
test = rpar (sum' 0 num) >>= (\a ->
       rpar (sum' num (num*2)) >>= (\b ->
       return (a,b)))

sum' :: Integer -> Integer -> Integer
sum' begin end = if begin < end
                   then begin + (sum' (begin + 1) end)
                   else begin
\end{lstlisting}

まず, Eval モナドが定義された, Control.Parallel.Strategies をロードし, Eval モナドを利用できるようにしている. 

Haskell のプログラムはmainという名前と実行したい関数を関連付けることで実行される. 
今回は, print (runEval test)が実行される. 

並列処理を行いたい箇所には, rpar を使う. 
rpar の引数とした関数は並列に実行可能であることを示すことができる.
Eval モナドの関数の型をみると, rpar は, a を モナドに包み, 逆にrunEval はモナドから a を取り出している（ソースコード\ref{eval}）.
rpar で並列化可能計算を示したあと, runEvalで実行するという流れになる. 

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

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

rpar を利用している test 関数は rpar モナドをbindで接続しているが, 入れ子構造となり書き方は煩雑となっている. 
Haskell にはモナドのために do 構文というシンタックスシュガーが用意されており, それを用いることでソースコード\ref{src:do}のように書くことができる. 
do 構文を使うことでbindの入れ子構造を簡潔に書ける. 

\begin{lstlisting}[label=src:do, caption=do構文]
test :: Eval (Integer, Integer)
test = do
    a <- rpar (sum' 0 num)
    b <- rpar (sum' num (num*2))
    return (a,b)
\end{lstlisting}

sum' は2つの引数をとって, 開始点から終了点までの値をすべて足し合わせる関数である. 
並列処理に負荷を与えるために使う. 
ifで, 開始点が終了点を超えてないか調べ, 超えてなければ再帰的に呼び出して足し合わせを行う. 

test で返ってくる型は, Eval (Integer, Integer)で, その後 runEval 関数を適用することで, (Integer, Integer)となる. 
そして最後にprint で出力される. 

Haskell は遅延評価を行うため, 必要となるまで式の評価が遅延される. 
今回の場合, mainのprintがなければそもそも計算が行われない（ソースコード\ref{src:donteval}）.

\begin{lstlisting}[label=src:donteval, caption=計算が行われない例]
main = return (runEval test)
\end{lstlisting}

出力することで, 値が必要となるため計算される.
また, testで返される2つの計算を1つだけ出力するようにした場合, 1つのみ計算され並列実行は行われない（ソースコード\ref{src:donteval2}）. 
fst は, (a,b)とあったとき aを取得する関数である. 

\begin{lstlisting}[label=src:donteval2, caption=並列実行されない例]
main = print (fst (runEval test))
\end{lstlisting}

Haskell で並列実行を行いたい場合は, 遅延評価に気をつける必要がある. 
rpar は単なるマーキングに過ぎず, rpar に渡したからといって直ちに並列実行が行われるわけではない.
rpar で作成した Eval モナドを runEval に渡したあと, 値が必要となるprintなどを行えば, 並列に実行可能な部分が並列に実行される. 

また, rpar を使用する際, 別の計算の値に依存する計算がある場合, その2つの計算は並列実行できない. 
例えば, ソースコード\ref{src:rpar}の場合は並列実行ができない. 

\begin{lstlisting}[label=src:rpar, caption=前の計算に依存した計算]
test2 :: Eval (Integer, Integer)
test2 = do
    a <- rpar (sum' 0 num)
    b <- rpar (sum' num (if a < num then a else (num*2)))
    return (a,b)
\end{lstlisting}