第1回 ラムダ抽象と関数適用

Arch Linux 上に ghc をインストールする方法は こちら．

Haskell は関数型言語の一種で，関数計算の連鎖でプログラムが動きます．
C 言語などにも関数はありますが，Haskell の関数はより数学的です．
まずは関数とは何かを説明します．


関数

Haskell において，関数は「値を変換するもの」です．
例えば，次のような，入力に$1$を加えて返す関数$f$を考えます．

$$
  f(x) = x + 1
$$

$x$が$1$だと$2$になります（$f(1) = 2$）．
関数$f$と$1$がくっつくと，$2$になってしまうのです．
$x = 2$の場合，$f(2) = 3$ですし，$x = 3$の場合は$f(3) = 4$になります．
つまり，関数というのは，定義という名のルールに従って，入力を出力に変換しているのです．

では，C言語の関数と何が違うのでしょうか？

Haskell の関数は，基本的に，同じ入力の時は同じ出力にならなければなりません．
上の関数$f$を見ると，どんな時でも同じ入力の時に同じ出力になります．
ところが，C言語の場合は同じ入力でも簡単に違う出力にできてしまいます．
入力が void 型（つまり入力なし）の時でも自由自在に出力を変えることができます．
逆に，入力だけ見ても出力を決めることができないということもできます．
Haskellの関数の基本は入力だけを見て出力が決まるという特徴があるので，「値を変換するもの」と見えるのです．


ラムダ抽象

「関数＝値を変換するもの」という考え方を発展させたものがラムダ抽象です．
中学や高校の数学において，関数というのは必ず名前がありました．
関数は値を変換してくれればいいだけなのに，必ず名前を決めてあげないと定義できません．
これをラムダ計算（lambda calculus）では，「入力をもらうと計算した結果を返すもの」を定義できるようにしました．
例えば，入力が$x$なら，$x + 1$を返す関数を

$$
  \lambda x . x + 1
$$

と書くことにしたのです．
最初の$\lambda$と$.$の間には入力の変数を１つ書くことができます．
また，$.$の後には変換式を書きます．
このラムダ式（$\lambda x . x + 1$）は上で定義した関数$f$の定義と同じ意味になります．
つまり，上の関数$f$の定義をラムダ計算流に書くと，

$$
  f = \lambda x . x + 1
$$

となるのです．
もちろん，わざわざ$f$なんていう名前を定義しなくても使えます．

2つの入力がある関数はどのように定義するのでしょうか？
次のように書くのが一般的です．

$$
  \lambda x . (\lambda y . x + y)
$$

この関数は$x$と$y$という2つの入力をもらうと，それを加えた値を返す関数という意味です．
$\lambda$の右側に１つしか変数を書けないと，$\lambda$が多くて分かりにくくなるので，以下のように複数の変数を書けるように拡張します．

$$
  \lambda x y . x + y
$$

ただし，これはあくまでも$\lambda x . (\lambda y . x + y)$の省略形です．


関数適用

関数適用は，実は，もう出てきています．
関数に入力を与えることを関数適用と言います．
具体的に，

$$
  f(1)
$$

が関数適用です．
関数$f$に$1$を入力していますよね．

ただ，Haskell ではカッコを使わずに，関数と引数の間にスペースを入れて，

$$
  f\; 1
$$

と書くことが多いです．
もちろん，$f$の代わりにラムダ抽象でもかまいません．

$$
  (\lambda x . x + 1)\; 1
$$

２つの入力がある場合は，次のように書きます．

$$
  (\lambda x y . x + y)\; 2\; 3
$$

$\lambda x y . x + y$は$\lambda x . (\lambda y . x + y)$の省略形でしたね．
つまり，入力は前から順番に受け取ることを意味します．
上のように３つを並べた関数適用は以下のように前からカッコが付いているものとみなします．

$$
    ((\lambda x y . x + y)\; 2)\; 3
$$

この関数適用は計算すると，次のようになります．

$$
\begin{eqnarray*}
  ((\lambda x y . x + y)\; 2)\; 3 & = & (\lambda y . 2 + y)\ 3 \\
          & = & 5
\end{eqnarray*}
$$


Haskellでの実装

では，Haskell で試してみましょう．
以下の関数を Lambda.hs という名前で保存します．

f = \x -> x + 1
g = \x y -> x + y

$\lambda$ を \ と書き， $.$ は -> と書きます．
関数 g の定義から分かるように，Haskell は $\lambda$ の省略形をサポートしています．

これを ghci に読み込ませます．

$ ghci Lambda.hs
GHCi, version 7.8.4: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( Lambda.hs, interpreted )
Ok, modules loaded: Main.
*Main> 

ここで以下のように関数適用を試すことができます．

*Main> f 1
2
*Main> g 2 3
5
*Main> (\x -> x * x) 10
100
*Main> 

ghci は :q と入力すると終了できます．

*Main> :q
Leaving GHCi.

雑談

ラムダ計算の式は

• 変数
• ラムダ抽象
• 関数適用

だけなんです．
上の説明では $1$ とか $2$ とか $+$ とか使っていましたが，本来のラムダ計算にはありません．
でも，あながちウソというわけでもないのです．
本来のラムダ計算でも，ちゃんと $1$ や $2$ などの数字や，足し算（$+$）を定義することができます．
チャーチ数（Church numerals）で調べれば定義の方法なども分かると思います．

自然数やその上の演算を定義できるどころか，ラムダ計算はどんなコンピューター上のプログラムも（原理的には）書くことができるのです．
たった3種類の式しかないのに．
これはラムダ計算が チューリング完全（Turing complete） だからです．
つまり，Haskell の本質は，ラムダ抽象と関数適用にあると言っても過言ではありません．
詳細には触れませんが，ラムダ計算には強力な記述力があることだけ理解してください．


今日はこの辺で．