(10)[ML] factorial関数の種々の定義

case文の使用

先ほどのfactorial関数の定義は,引数の位置に処理したい値の形(0か一般のnか)を書き,関数定義を場合分けで定義していた,この構文は,以下のcase文を使った定義の省略形である,

fun factorial2 n =
  case n of
    0 => 1
  | x => x * factorial (x - 1)

case構文は,

処理したい値のパターン => 処理内容

の形のフレーズを|で区切って並べたものである,パターンには変数や数値を書くことができる,変数は「処理内容」の部分で使用することができる,パターンに_と書くと任意の値の意味である,これを使うと,以下のように書ける,

fun factorial2 n =
  case n of
    0 => 1
  | _ => n * factorial (n - 1)

if文の使用

上のようなパターンマッチングがMLにおける場合分けや条件分岐の基本構文であるが,パターンでは表しきれない条件などはif文を用いる,factorialはif文を使って以下のようにも書くことができる,

fun factorial3 n =
  if n = 0 then 1
  else n * factorial (n - 1)

ここで,n = 0は代入文ではなく,nが0と等しいか否かをテストする式である,テストの結果はtrueかfalseの値である,if文は条件部分の式の結果がtrueであればthenの後に書かれた式を計算しその結果を返し,条件部分の式の結果がfalseであればelseの後に書かれた式の結果を返す,この例の場合,もしn=0がtrueなら1を返しそうでなければn * factorial (n - 1)の式の結果を返す,

ループ(末尾再帰)による実現

以上の階乗の定義に対応した再帰的な関数定義は,理解しやすく簡潔な定義であるが,関数呼び出しのオーバーヘッドのため,whileやforを用いたCの繰り返し演算と同等の効率よい実行は困難である,しかし,この事実は,MLのプログラムが対応するCのプログラムに比べて効率が悪いことを意味しない,最後に示したCの再帰的なプログラムは以上のMLプログラムと同様の振る舞いをする,

では,Cの繰り返し演算に対応するMLのプログラムは書けるであろうか,厳密な答えは困難であるが,概ね「書ける」といってよい,以下がそのプログラムである,

fun loop (0,s) = s
  | loop (n,s) = loop(n-1, s * n)
fun factorial4 n = loop (n, 1)

この定義では,補助関数loopを使用している,loopはもし最初の引数が0なら2番目の引数を返し,そうでなければ,引数を変更して自分自身を呼びだしている,この場合,もとの引数がその後使用されることはなく,また,関数呼び出しの後にさらに行う処理も残っていない,したがって,この再帰的なloop呼び出しは,現在の引数を直接変更し自分自身の最初のコードにジャンプすることで実現される,すなわちループと同じである,このような性質をもつ再帰関数を末尾再帰関数とよぶ,

以前書いた以下のCプログラムと比較してみよう.

int factorial (int n) {
  int s = 1;
  while (n > 0) {
    s = s * n;
    n = n - 1;
  }
 return s;
}

factorialからsの引数を1でloopを呼び出すこが,Cでwhileの繰り返しに入る前にsを1に初期化することにとに対応し,関数の引数の値による場合分けがwhileの繰り返しの条件判定に対応していることに注意すれば,これら2つのプログラムはほぼ同等の内容を記述していることが理解できる.

この末尾再帰による関数の定義は,MLで効率よいコードを書く基本技術である,この概念に初めて触れる読者はこの機会にぜひ補足:末尾再帰の考え方を修得しておこう,

let構文

上記の定義で使っているloop関数はfactorial関数を定義するための補助関数である,このような関数はトップレベルに定義するのではなく,それを使用する関数の内部関数として定義すると,全体としてより構造化されたプログラムとなる,このためには以下のlet構文を利用して,以下の様に書く,

fun factorial5 n =
  let
    fun loop (0, s) = s
      | loop (n, s) = loop(n - 1, s * n)
  in
    loop (n, 1)
  end

let構文の構造は以下の通りである,

let 定義列 in 式 end

定義列はinとendの中だけで有効であり,この構文全体はinとendの中の式を計算する一つの式である,関数定義以外に式の書けるところにはどこにでも書くことができる,

以上説明したようにlet文やif文は,C言語と違い,それ自身式である,この点を理解することがMLのプログラミング理解の鍵である,そこで補足:末尾再帰の考え方を習得したら,次に式の組み合わせによるプログラミングの考え方を学ぼう,


[ トップ | 目次 | 前ページ | 次ページ ]