Haskell は手軽だ

Haskell は難しいという評判だが、ちょっとした指標を計算するときなどは、Haskell でやるのが一番手軽だ。たとえば、100万円を年2％の複利で20年借りるといくらになるかというのは、ghci をつかうと、

Prelude> 100 * 1.02 ** 20
148.594739597835

で48万円の利子がつくことになるのがわかる。このように、思いついたことをパッパと実行してみることができる。

また、ちょっと技巧的になるが、フィボナッチ数列の値を知りたい時も、

Prelude> fib = 0:1:zipWith (+) fib (tail fib)
Prelude> take 10 fib
[0,1,1,2,3,5,8,13,21,34]

のように一行で計算できてしまう。数行のプログラムを組まないと試せない場合に比べ、とにかく、手軽なのだ。

Haskell は難しい

しかしながら、ループを全て再帰的プログラムで表現しないといけなかったり、変数への再代入ができなかったり、今までの手続き型のプログラムとは発想がちがうのでなかなか馴染めない部分もある。便利かもしれないが勉強が大変なのではないかと敬遠する人も多いだろう。

しかし、結局のところ Haskell のプログラムの動作は全て、変数を値や式で置き換えることで説明がつく。たとえば、次のような関数を定義したとしよう。

f x y = x + y

この関数に引数 x = 1, y = 2 を与えると, 3 という値が得られるが、

Prelude> f x y = x + y
Prelude> f 1 2

3

これは、関数 f x y の変数 x, y にそれぞれ x = 1 と　y = 2　を代入した式を計算していることになる。

f 1 2 = 1 + 2 = 3

もうちょっと複雑な例を考えてみよう。　g x = x * x を　f 1 2 に適用させた　g ( f 1 2 ) の出力は次のようになるが、

Prelude> g x = x * x
Prelude> g (f 1 2)
9

これも、

g (f 1 2) = g (1 + 2) = g 3 = 3 * 3 = 9

のように、次々に式を展開していって値が得られているのがわかる。実は、再帰的定義のようなループ処理のプログラムも、単なる式の展開で説明ができるのだ。

Haskellでは再帰的定義も式の展開で理解できる

Haskellでは手続き型言語のループの処理は全て再帰的定義で行われる。再帰的定義とは関数の定義をその関数自身で行うやり方だ。抽象的に言うと分かりにくいが、階乗(factorial)の計算プログラムなら一度は作ったことがあるはずだ。C言語の入門書にも階乗の計算プログラムは出てくる。

Hugsで階乗の計算をすると次のようになる。

Prelude> fact 0 = 1; fact n = n * fact (n-1)
Prelude> fact 5
120

fact n は n の階乗を計算する関数だ、上の例では、再帰的定義で関数の定義が行われている。再帰的定義とは定義の = の左にも定義される関数が現れる。自分自身を定義するのに定義される当の関数を使うのだから変な感じがする。そこで、定義の部分を抜き出すと次のようになる。

fact 0 = 1
fact n = n * fact (n-1)

たった2行で階乗の関数が定義されること自体がすごいが、プログラムの意味をみてみよう。まず fact n の引数の値が n = 0 の時は、fact 0 = 1 だ。0! = 1 だからである。次に n > 0 の時は、fact n = n * fact (n-1) である。n の階乗の値は、n と (n-1)! の積になる。すなわち、n! = n * (n-1)! だ。

それでは、この関数の定義で fact 5 がどのように計算されるかを見てみよう。

fact 5
= 5 * fact 4
= 5 * 4 * fact 3
= 5 * 4 * 3 * fact 2
= 5 * 4 * 3 * 2 * fact1
= 5 * 4 * 3* 2 * 1 * fact 0
= 5 * 4 * 3 * 2 * 1 * 1
= 120

このように、fact 5 を定義に沿って次々に展開していくことで計算が実行される。Haskell のプログラムはどれも、このように単純に式を展開していくことでそのプログラムが実行される。Haskell のプログラムがどのように実行されるのかを知るためには、単にそれを定義に沿って展開していくだけでいいのだ。

Haskell のプログラムの実行は、例外なく式の展開だと考えると、暗号に見えていた Haskell プログラムが理解できるものに思えてくる。

foldr と foldl

Haskell 標準の Prelude ライブラリの高階関数のうちで、map と filter は直感的にわかりやすい。

Prelude> map (*2) [1..10]
[2,4,6,8,10,12,14,16,18,20]
Prelude> filter (>5) [1..10]
[6,7,8,9,10]

しかし、foldr と foldl の畳み込み関数の使い方については理解するのが難しい。ところが、今までのように数式を展開してみると意外に分かりやすい。

まず、foldr について見てみる。foldr の型を :t コマンドで表示してみる。

Prelude> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

一見しても何を言っているのかわからないが。(a -> b -> b) は第1引数が2引数の関数であることを示している。例えば x + y の + である。第2引数は b 型のデータ、第3引数は a 型のデータのリスト [a]で、値は b 型の値になる。第2引数と第3引数の型が b と a で違っているが、これは第1引数の値が a 型の値と b 型の値を取り b 型の値を返す関数だからだ。

抽象的な説明ではわかりにくいので、forldr (+) 0 [1,2,3,4] の動作を見てみよう。コンピュータにたずねてみる。

Prelude> foldr (\x y -> "(" ++ x ++ " + " ++ y ++ ")") "0" ["1","2","3","4"]
"(1 + (2 + (3 + (4 + 0))))"

これは + の右に [1,2,3,4] の 1 を置き、左に foldr 0 [2,3,4] の値を置くという操作を繰り返していることを示している。これを、次々に手動で展開すると次のようになる。

foldr (+) 0 [1,2,3,4]
= (1 + (foldr 0 [2,3,4]))
= (1 + (2 + (foldr 0 [3,4])))
= (1 + (2 + (3 + foldr 0 [4]))))
= (1 + (2 + (3 + (4 + foldr 0 []))))
= (1 + (2 + (3 + (4 + 0))))

これは再帰的定義で行われる次の計算と同じである。

Prelude> fold [] = "0"; fold (x:xs) = "(" ++ x ++ " + " ++ (fold xs) ++ ")"
Prelude> fold ["1","2","3","4"]
"(1 + (2 + (3 + (4 + 0))))"

foldr は再帰関数の base case と recursive case をひとつにまとめたものと考えることができる。したがって、次の計算が階乗になるのも納得できる。

Prelude> foldr (*) 1 [1,2,3,4,5]
120

foldr の動作はわかったが、foldl の動作はどうなるのだろうか。これもコンピュータに聞いてみるのが早い。

Prelude> foldl (\x y -> "(" ++ y ++ " + " ++ x ++ ")") "0" ["1","2","3","4"]
"(4 + (3 + (2 + (1 + 0))))"

foldr の場合は foldr とは違って畳み込みの計算が + の左に向かって進んでいくのが分かる。

+ や * の計算は可換なので foldr と foldl の値は同じになる。しかし、subtract 関数の場合は可換ではないのでその値は等しくない。

Prelude> foldr subtract 0 [1,2,3,4]
-10
Prelude> foldl subtract 0 [1,2,3,4]
2

foldr、foldl のように抽象的な関数でも Haskell の計算はすべて式の展開で行われると考えるとその仕組みがわかりやすくなる。