Ch.7 MLプログラミング入門

§ 7.7. 再帰的な関数

前節で学んだfun構文は再帰的な定義を許します. すなわち,この構文で定義される関数funNameを,関数定義本体 exprの中で使用することができます. このような再帰的な関数定義は,以下のような手順で設計していけば, 通常の算術関数と同じように自然に定義できるようになります.

  1. 関数funNameの振る舞いをあらかじめ想定する.

  2. 想定された振る舞いをする関数funNameがあると仮定し, 受け取った引数がparamの場合に返すべきか値を表す式expr を定義する.

例えば,第7.2節で紹介した階乗を計算す る関数factは以下のように設計できます.

  1. factを階乗を計算する関数と想定します.

  2. 階乗を計算する関数factを使い,階乗の定義に従い,返すべき値を 以下のように定義する.

    1. 引数が0の場合,0の階乗は1であるから,1を返す.

    2. 0以外の一般の引数nの場合,階乗の定義から, n * fact (n - 1)を返す.

この2つの場合を単に書き下せば,以下の定義が得られます.

# fun fact 0 = 1
>      | fact n = n * fact (n - 1);
val fact = fn : int -> int

以上の考え方に従い種々の再起関数を簡単に定義できます. たとえば,すべての数の和を求める関数sumや引数nに対して与 えられた定数cn乗を計算するpowerなども,これら関数がすでにあ ると思うことによって,以下のように簡単に定義できます.

fun sum 0 = 0
  | sum n = n + sum (n - 1)
fun power 0 = 1
  | power n = c * power (n - 1)

sumpowerが想定した振る舞いをすると仮定すれば, 関数が返す値は正しいので,関数全体の定義も正しいことがわかります.