(10-1)[ML] 補足:末尾再帰をマスターする

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


末尾再帰は効率よいMLコードを書く上で必須の道具である。この概念抜きには、MLの再帰関数を理解した/説明したとは言い難い。そこで、この概念を身につけよう。

末尾再帰は、おそらく一般には「MLプログラミングの初歩」とは見なされておらず、チュートリアルや入門書の対象となっていないかもしれない。しかし、我々はCの初歩であるループの考え方をすでに学んでいる。この考え方を参考にすれば、末尾再帰も十分に「MLプログラミングの初歩」の範囲内である。

ループ状態を引数として末尾コールする

末尾再帰は関数型言語におけるループするコードであり、その設計方針はループの考え方とほぼ同じである。

繰り返しコード設計の基本は,

  1. 求める値に至る(それを特別な場合として含む)計算の途中状態を設計し、
  2. 計算の途中結果の値を保持するための変数と
  3. 計算の進行状態を保持する変数を用意し,
  4. これら変数を更新するコードを書く

ことであった.末尾再帰の場合も,最後の点を除けば,方針はこれと同じである.末尾再帰の場合,更新するための変数を関数内に用意し,それら変数を更新するコードを書くかわりに,

  1. 計算の途中結果を持つ変数と状態変数を引数としてとる
  2. 「変数を次の値に更新する」代わりに「次の値を指示して再帰呼び出し(末尾呼び出し)する」

とすればよい.

具体的に,以前ループの考え方で学んだfactorialの例を見てみよう.

  • 1からnまでの積を求める(前のfactorialの例)
    • 計算結果を持つ変数:s
    • 計算の状態を保持する変数:i
    • 途中の計算状態:s = i * (i + 1) * ... * n
    • 最終状態:i = 0

であった.これから,以下の方針で関数を設計すればよいことが分かる.

  1. sとiの二つの引数を取る.
  2. 関数は i = 0 ならsをそのまま返し終了する
  3. それ以外は,sにiを掛けたものとi+1を新たな引数として末尾コール(tail call)する.

これをSMLでコードすると以下のようになる.

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

sとiの初期値はそれぞれ1とnであるから,この関数をfact(1,n)で呼び出せばfactorial nが計算できる.以前学んだように通常letを用い以下のようなコードを書く.

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

fact関数はfactorial nの中に定義されているので,factで使用されるnは元々のfactorial関数の引数nである.

種々の末尾再帰関数

では,ループの考え方で定義した設計した各関数を,以上のように解釈しなおし,末尾再帰のMLコードとして表現してみよう.

  • 1からnまでの総和を求める
    • 計算結果を持つ変数:s
    • 計算の状態を保持する変数:i
    • 途中の計算状態:s = i + (i+1) + ... + n
    • 最終状態:i = 0
fun sum n =
  let
    fun loop (s,0) = s
      | loop (s,i) = loop(s + i, i - 1)
  in
    loop(0,n)
  end
  • 1からnまでの整数の2乗の和を求める
    • 計算結果を持つ変数:s
    • 計算の状態を保持する変数:i
    • 途中の計算状態:s = i*i + (i+1)*(i+1) + ... + n * n
    • 最終状態:i = 0
fun sigma2 n =
  let
    fun loop (s,0) = s
      | loop (s,i) = loop(s + i*i, i - 1)
  in
    loop(0,n)
  end
  • 1からnまでの整数の3乗の和を求める
    • 計算結果を持つ変数:s
    • 計算の状態を保持する変数:i
    • 途中の計算状態:s = i * i * i + (i+1) * (i+1) * (i+1) + ... + n*n*n
    • 最終状態:i = 0
fun sigma3 n =
  let
    fun loop (s,0) = s
      | loop (s,i) = loop(s + i*i*i, i - 1)
  in
    loop(0,n)
  end
  • xとyの積を足し算を使って計算する(積はyをx回足したもの)
    • 計算結果を持つ変数:s
    • 計算の状態を保持する変数:i
    • 途中の計算状態:s = xをi回足した結果
    • 最終状態:i = x
fun times(x,y) =
  let
    fun loop (s,0) = s
      | loop (s,i) = loop(s + x, i - 1)
  in
    loop(0, y)
  end
  • 与えられた数nをk乗する.
    • 計算結果を持つ変数:s
    • 計算の状態を保持する変数:i
    • 途中の計算状態:s = nの(k - i)乗
    • 最終状態:i = 0
fun power(n,k) =
  let
    fun loop (s,0) = s
      | loop (s,i) = loop(s * n, i - 1)
  in
    loop(1, k)
  end
  • 初項A(0)が1公差が2の等差数列のn番目の項A(n).
    • 計算結果を持つ変数:s
    • 計算の状態を保持する変数:i
    • 途中の計算状態:s = i番目の項
    • 最終状態:i > n
fun A(n) =
  let
    fun loop (s,i) =
      if i > n then s
      else loop(s + 2, i + 1)
  in
    loop(1, 1)
  end
  • 初項B(0)が1公比が2の等比数列のn番目の項B(n).
    • 計算結果を持つ変数:s
    • 計算の状態を保持する変数:i
    • 途中の計算状態:s = i番目の項
    • 最終状態:i > n
fun B(n) =
  let
    fun loop (s,i) =
      if i > n then s
      else loop(s * 2, i + 1)
  in
    loop(1, 1)
  end
  • 初項C(0) = 1でC(n) = 2 + 3 * C(n-1)なる漸化式の一般公
    • 計算結果を持つ変数:s
    • 計算の状態を保持する変数:i
    • 途中の計算状態:s = i番目の項
    • 最終状態:i > n
fun C(n) =
  let
    fun loop (s,i) =
      if i > n then s
      else loop(2 + 3 * s, i + 1)
  in
    loop(1, 1)
  end;

テスト

以上の関数定義をファイルtailCalls.smlに書き出し,テストしてみよう.以下のような出力が得られるはずである.

SML# 0.20 (2007-04-19 14:20:41)
# use "tailCalls.sml";
val factorial = fn : int  -> int
val sum = fn : int  -> int
val sigma2 = fn : int  -> int
val sigma3 = fn : int  -> int
val times = fn : int * int  -> int
val power = fn : int * int  -> int
val A = fn : int  -> int
val B = fn : int  -> int
val C = fn : int  -> int
# factorial 10;
val it = 3628800 : int
# sum 10;
val it = 55 : int
# sigma2 10;
val it = 385 : int
# sigma3 10;
val it = 3025 : int
# times(2,3);
val it = 6 : int
# power(2,3);
val it = 8 : int
# A 10;
val it = 21 : int
# B 10;
val it = 1024 : int
# C 10;
val it = 118097 : int
#

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

Last modified:2007/05/15 10:58:29
Keyword(s):
References:[ML&Cチュートリアル 目次] [(10)[ML] factorial関数の種々の定義]