Haskell あれこれ 再帰の種類(数値型)

Haskell の関数で再帰的定義をする場合引数の型の種類によって分類するのが便利だ。引数の型の種類とは、数値型、リスト型、木構造型 の3つだ。

1.数値型

数値型の引数をとる再帰関数の代表は、階乗だ。階乗を求める関数 fact (x) はつぎのように定義される。

fact (x) = | 0 (x = 0 のとき)
              | n * fact (n-1) (x > 0 のとき)

この定義で行くと、fact (0) = 1 だ。引数が0以上の場合はたとえば、fact (4) は、

fact (4) = 4 * fact(3) = 4 * (3 * fact(2)) = 4 * (3 * (2 * fact(1)))

= 4 * (3 * (2 * (1 * fact(0)))) = 4 * (3 * (2 * (1 * 1)))) = 24

のように展開が進み終了条件に達した時点で数値の計算が始まる。このような関数はC言語でもプログラムすることができる。

/* 階乗n!を計算する */
int fact(int n) {
if (n==0) return 1; /* 脱出条件。0!は1である */
else return fact(n-1)*n; /* n!は(n-1)!にnを乗じたもの。再帰呼び出し */
} (Wikipedia 「再帰」 より引用)

自分自身を、自分自身の中から呼び出すという理解しがたい再帰呼び出しをおこなっているが、これは、関数呼び出しに伴うスタック操作というC言語の実装の仕組み利用して巧みに上で述べた式の展開と同じような効果を作っている。しかし、実装のことは知らなくてもC言語で再帰呼び出しができるのは分かっているので、簡単な再帰関数なら、そう悩まなくてもC言語でプログラムすることができる。

ところで、この関数 fact (x) を Haskell でプログラムすると次のようになる。

fact :: Integer -> Integer
fact 0 = 1
fact n | n > 0 = n * fact (n-1)

型の定義はしておいたほうが便利だが、慣れないうちは省略してもかまわない。そうすると、これは、上の数学的な定義をそのまま逐語的にプログラムに直しただけだ。if ~ then ~ else 文がないが、Haskell は関数を定義するときに引数のパターンで値を変えることができるからだ。

上のプログラムで2行目は引数が 0 の時の値を設定している。次の行は n | n > 0 が引数のパターンで n が正の整数の場合をあらわしている。

したがって上のプログラムでは、fact 関数の引数が 0 の時は整数 1 が返される。また、引数が正の整数のときは、fact n = n * fact (n-1) = n * (n-1) * fact (n-2) = ... という式の展開が終了条件の fact 0 が現れるまで実行され、終了条件の fact 0 が現れた時点で、展開式の fact 0 が 1 に置き換えられ、計算が始まってその値が整数値として返される。

普通の文章で表すと上のプログラムの説明がやけに長くなってしまったが、再帰的定義が、展開したときの煩雑な手続きをコンパクトに表現してくれるからだ。

いずれにせよ、引数が数値の場合の関数の再帰的定義は、Haskell の場合は、引数のパターン表記を利用して、定義の数式をほぼそのままの形でプログラムできる。また、Haskell のプログラムに引数が数値型の再帰関数が現れたら。f(x)のような数学の表記に直して数式を展開していくとその意味がよく分かる。
[PR]
by tnomura9 | 2009-08-20 12:27 | Haskell | Comments(0)
<< Haskell あれこれ 再帰... Haskell あれこれ 再帰 >>