お気楽 Standard ML of New Jersey 入門

●相互再帰

相互再帰とは、関数 foo が関数 bar を呼び出し、bar でも foo を呼び出すというように、お互いに再帰呼び出しを行っていることをいいます。SML/NJ はコンパイル時に型チェックを行うプログラミング言語なので、foo から bar を呼び出そうとしても、bar が未定義の場合はコンパイルでエラーになります。このため、SML/NJ では相互再帰を次のように定義します。

fun
    最初の関数定義
and
    2 番目の関数定義
and
    .....
and
    n 番目の関数定義

相互再帰を行っている関数を and でつなげて定義します。SML/NJ の場合、and は論理演算子ではありません。論理演算子には andalso を使います。ご注意くださいませ。

それでは簡単な例を示しましょう。次のリストを見てください。

リスト : 相互再帰

fun foo 0 = true
|   foo n = bar(n - 1)  
and 
    bar 0 = false
|   bar n = foo(n - 1)

このプログラムは関数 foo と bar が相互再帰しています。foo と bar が何をしているのか、実際に動かしてみましょう。

- bar 3;
val it = true : bool
- bar 2;
val it = false : bool
- bar 1;
val it = true : bool
- foo 3;
val it = false : bool
- foo 2;
val it = true : bool
- foo 1;
val it = false : bool

結果を見ればおわかりのように、foo は n が偶数のときに真を返し、bar は n が奇数のときに真を返します。なお、このプログラムはあくまでも相互再帰の例題であり、実用的なプログラムではありません。

●末尾再帰

再帰定義のなかで、最後に再帰呼び出しを行う場合を「末尾再帰」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに「末端再帰」とか「終端再帰」と訳すことがあります。末尾再帰は簡単な処理で「繰り返し」に変換することができます。これを「末尾再帰最適化」^[*2] といいます。

Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルするときに、この最適化を行う処理系があります。なかには Scheme のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。M.Hiroi は SML/NJ の仕様をよく理解していないので断言はできませんが、SML/NJ でも末尾再帰最適化が行われていると思います。

たとえば、階乗を求める関数 fact を思い出してください。

リスト : 階乗の計算

fun fact 0 = 1
|   fact n = n * fact(n - 1)  

fact は最後に x と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると、次のようになります。

リスト : 階乗の計算 (末尾再帰)

fun facti(0, a) = a
|   facti(n, a) = facti(n - 1, n * a)  

fun fact n = facti(n, 1)

fact は関数 facti を呼び出すだけで、実際の計算は facti で行っています。 facti は最後の再帰呼び出しで facti の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議な感じがしますね。まあ、そこが再帰呼び出しの面白いところです。このプログラムでは変数 a の使い方がポイントです。

たとえば fact 4 を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算しています。このとき、計算の途中経過を変数 a に記憶しているのです。fact の呼び出し (末尾再帰最適化前の動作) を図に示すと、次のようになります。

facti(4, 1)
  facti(3, 4)
    facti(2, 12)
      facti(1, 24)
        facti(0, 24)
        => a の値 24 を返す
      => 24
    => 24
  => 24
=> 24

変数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。純粋な関数型言語の場合、while や loop などの繰り返しが用意されていない言語があります。また、論理型言語の Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。

ところで、関数 facti は fact からしか呼び出されていません。このような場合、facti は let で局所的な関数として定義するといいでしょう。プログラムは次のようになります。

リスト : 階乗の計算 (末尾再帰)

fun fact n =
  let
    fun facti(0, a) = a
    |   facti(n, a) = facti(n - 1, n * a) 
  in
    facti(n, 1)
  end

リストを反転する関数 reverse も末尾再帰に変換することができます。次のリストを見てください。

リスト : リストの反転 (末尾再帰)

fun reverse xs =
  let
    fun rev1(nil, ys) = ys
    |   rev1(x::xs, ys) = rev1(xs, x::ys) 
  in
    rev1(xs, nil)
  end

関数 rev1 は、リストの先頭要素を引数 ys の先頭に追加していきます。したがって、rev1(x, nil) と呼び出せば、リストを反転することができます。rev1 の呼び出しを図に示すと、次のようになります。

rev1([1, 2, 3, 4], nil)
  rev1([2, 3, 4], [1])
    rev1([3, 4], [2, 1])
      rev1([4], [3, 2, 1])
        rev1(nil, [4, 3, 2, 1])
        => ys の値 [4, 3, 2, 1] を返す
      => [4, 3, 2, 1]
    => [4, 3, 2, 1]
  => [4, 3, 2, 1]
=> [4, 3, 2, 1]

このように、引数 ys には反転途中の値が格納されていることがわかります。

●フィボナッチ関数の高速化

今度は累算変数を使って、二重再帰を末尾再帰へ変換してみましょう。例題としてフィボナッチ数列を取り上げます。フィボナッチ関数の定義とプログラムを再掲します。

リスト : フィボナッチ関数

fun fibonacci n =
  if n < 2 then n
  else fibonacci(n - 1) + fibonacci(n - 2)  

このプログラムは二重再帰になっているので、とても時間がかかります。二重再帰を末尾再帰に変換すると、プログラムを高速に実行することができます。プログラムは次のようになります。

リスト : フィボナッチ関数(末尾再帰)

fun fibonacci n =
  let
    fun fibo(0, a, _) = a
    |   fibo(n, a, b) = fibo(n - 1, b, a + b)
  in
    fibo(n, 0, 1)
  end

累算変数 a と b の使い方がポイントです。現在のフィボナッチ数を変数 a に、次の値を変数 b に格納しておきます。あとは a と b を足し算して、新しいフィボナッチ数を計算すればいいわけです。fibo の呼び出しを図に示すと、次のようになります。

fibo(5, 0, 1)
  fibo(4, 1, 1)
    fibo(3, 1, 2)
      fibo(2, 2, 3)
        fibo(1, 3, 5)
          fibo(0, 5, 8)
          => a の値 5 を返す
        => 5
      => 5
    => 5
  => 5
=> 5

二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行できるでしょう。

このように、末尾再帰は実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも末尾再帰でプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、末尾再帰に変換するとプログラムがめちゃくちゃ複雑になってしまう、というアルゴリズムもあります。したがって、とくに問題がなければ、再帰定義をむりやり末尾再帰へ変換する必要はないでしょう。わかりやすいプログラムがいちばんだと思います。

●問題

次の再帰関数を末尾再帰に直してください。

1. 整数 1 から n までの総和を求める関数 sum n
2. 整数 1 から n までの平方数の総和を求める関数 square_sum n
3. 整数 1 から n までの三乗数の総和を求める関数 cube_sum n

●解答

リスト : 解答例

fun sum n =
  let
    fun sumi(0, a) = a
    |   sumi(n, a) = sumi(n - 1, a + n)
  in
    sumi(n, 0)
  end

fun square_sum n =
  let
    fun sumi(0, a) = a
    |   sumi(n, a) = sumi(n - 1, a + n * n)
  in
    sumi(n, 0)
  end

fun cube_sum n =
  let
    fun sumi(0, a) = a
    |   sumi(n, a) = sumi(n - 1, a + n * n * n)
  in
    sumi(n, 0)
  end

val sum = fn : int -> int
val square_sum = fn : int -> int
val cube_sum = fn : int -> int

val it = () : unit
- sum 100;
val it = 5050 : int
- square_sum 100;
val it = 338350 : int
- cube_sum 100;
val it = 25502500 : int