Haskellでは再帰的定義も式の置き換え(展開)

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

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

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

fact n は n の階乗を計算する関数だ、上の例では、where 以下の2行がその定義だ。定義の部分を抜き出すと次のようになる。

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 プログラムが理解できるものに思えてくる。

追記

上の式の展開は括弧を使って表現すると、展開の構造が分かりやすい。

fact 5
= 5 * (fact 4)
= 5 * (4 * (fact 3))
= 5 * (4 * (3 * (fact 2)))
= 5 * (4 * (3 * (2 * (fact 1))))
= 5 * (4 * (3 * (2 * (1 * (fact [])))))
= 5 * (4 * (3 * (2 * (1 * (1))))))

この括弧を使った展開を利用すると foldr と foldl の違いがはっきりと分かる。
[PR]
by tnomura9 | 2010-10-08 23:19 | Haskell | Comments(0)
<< リストの総和も式の展開で計算 Haskell のプログラムは... >>