SML# - Tutorial/010-1 Diff

  • Added parts are displayed like this.
  • Deleted parts are displayed like this.

[ [[トップ |Tutorial]]| [[目次|Tutorial/000]] | [[前ページ|Tutorial/010]] | [[ 次ページ |Tutorial/011]] ]
----
末尾再帰は効率よいMLコードを書く上で必須の道具である。この概念抜きには、MLの再帰関数を理解した/説明したとは言い難い。そこで、この概念を身につけよう。

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

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

繰り返しコード設計の基本は,
# 求める値に至る(それを特別な場合として含む)計算の途中状態を設計し、
# 計算の途中結果の値を保持するための変数と
# 計算の進行状態を保持する変数を用意し,
# これら変数を更新するコードを書く
ことであった.末尾再帰の場合も,最後の点を除けば,方針はこれと同じであ
る.末尾再帰の場合,更新するための変数を関数内に用意し,それら変数を更新するコードを書くかわりに,
# 計算の途中結果を持つ変数と状態変数を引数としてとる
# 「変数を次の値に更新する」代わりに「次の値を指示して再帰呼び出し(末尾呼び出し)する」
とすればよい.

具体的に,以前ループの考え方で学んだfactorialの例を見てみよう.
* 1からnまでの積を求める(前のfactorialの例)
** 計算結果を持つ変数:s
** 計算の状態を保持する変数:i
** 途中の計算状態:s = i * (i + 1) * ... * n
** 最終状態:i = 0
であった.これから,以下の方針で関数を設計すればよいことが分かる.
# sとiの二つの引数を取る.
# 関数は i = 0 ならsをそのまま返し終了する
# それ以外は,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
#
----
[ [[トップ |Tutorial]]| [[目次|Tutorial/000]] | [[前ページ|Tutorial/010]] | [[ 次ページ |Tutorial/011]] ]