Haskell あれこれ 再帰

Haskell では関数やデータの再帰的定義がよく使われる。この再帰的定義の仕組みが最初は理解するのが難しいことが多く、Haskell を学ぶのに壁があるとすれば、最大の壁はこの再帰的定義だろう。

一般に関数の定義は、f(x)=x*x のように左に関数名と変数(引数)右に関数の値(戻り値)の計算法が記述される。Haskell の関数は数学の場合とほぼ同じやり方で定義される。たとえば、引数に整数をとり戻り値にその2乗を返す関数 square は、

square x = x * x

で定義できる。この場合、関数の名前は式の左側にしか現れない。新しい関数を定義するのに既に動作が確定している操作を組み合わせるわけで納得できる。ところが、関数の再帰的定義の最大の特徴はこの関数名が式の右側にも現れると言うことだ。例えば階乗の計算の再帰的定義 (recursive case) は次のようになる。

fact n = n * fact (n-1)

関数を定義するのに、まだ定義のはっきりしていない自分自身を使うという変な定義のしかたなので奇妙な感じがする。しかし、よく見ると等式の右と左では関数の引数の値が違う。これは、どういう意味なのだろうか。たとえば、n = 4 の場合を考えてみよう。

fact 4 = 4 * fact 3 = 4 * (3 * fact 2) = 4 * (3 * (2 * fact1)) = ...

のように右の関数を左の定義で置き換えていくことによって、関数の定義がつぎつぎに展開されていくのが分かる。この時に左側に現れる fact n の引数は常に右側の fact の引数より一つだけ小さい (reduce) ことに注意する。このままでは、関数の展開は永遠に続いてしまうが、fact n の定義で、fact 1 = 1 という終了条件(base case) が与えられていると、上の定義は有限回で終了する。つまり、

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

のように定義を展開する度に fact の引数が減少していき、ついには終了条件に達してすべての展開が数値にかわり、定義が終了する。この様に定義の展開が有限回で終了すればあとは展開された数式を計算することによって、fact 4 の値を決定することができる。関数を定義するのに自分自身を使ってもちゃんと値が求められる仕組みがあるのだ。

したがって、関数の定義にその関数を使うという再帰的定義の変則的な定義法だが次の二つの要件を満たして入れば、きちんと動作することが分かる。

1)明示的な終了条件 (base case) があること。
2)等号の右の関数を定義するのに左の関数を使うとき (recursive case) は、左の関数の引数の値が減少 (reduce) している必要があること。

この二つの要件をおさえていれば、関数を定義するのに、定義する当の自分自身を使うという理解しがたい再帰的定義の仕組みを分かって、複雑な現象をコンパクトに記述できる再帰的定義のパワーを活用することができる。

ちなみに、上の fact 関数のHaskell によるプログラムは次のようになる。

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

また、再帰的定義を展開するのに、右の関数を左の定義で置き換えるという操作を続けたが、同じ値の式を置き換えるというのが Haskell の本質的な動作だ。置き換えられた式は常に同じ値をとるので、式の評価が実行の順序によらない、プログラムの正しさや、アルゴリズムの改良を数学的に検証できるなどという関数言語の特徴が現れてくる。

次の記事では、Haskell に現れる再帰的定義の形態について検討してみる。再帰的定義と言ってもパターンは限られているので、数種のパターンの性質に慣れれば再帰的定義で混乱することはなくなる。
[PR]
by tnomura9 | 2009-08-19 06:33 | Haskell | Comments(0)
<< Haskell あれこれ 再帰... Haskell 記事リスト >>