関数の中で引数以外の局所変数を定義できると便利な場合があります。SML/NJ の場合、let ... in ... end で局所変数を定義することができます。let の構造を示します。
let
val name1 = expr1
val name2 = expr2
...
val nameN = exprN
in
expr
end
let と in の間に宣言を書きます。局所変数は val 宣言で定義します。ここで fun 宣言を使うと、局所的な関数を定義することができます。宣言はいくつでも定義することができます。宣言が複数ある場合はセミコロン ( ; ) で区切ります。[*1] そして、in と end の間に評価する式 expr を定義します。let で定義された局所変数の有効範囲は let の中だけです。let は局所変数を生成して式 expr を評価し、その結果が let の返り値になります。
それでは簡単な例題として累乗を求める関数 pow を作ってみましょう。累乗は x の n 乗という x を n 回掛ける計算です。累乗は x の右上に小さく n を書くことで表されますが、ここでは x ** n と書くことにします。
累乗の計算 pow( x, y ) = x ** y; x ** 3 = x * x * x; x ** 4 = x * x * x * x; x ** 5 = x * x * x * x * x;
今回のプログラムでは、引数 x を実数、y を整数とします。そうすると、x ** y は次のように定義することができます。
x ** 0 = 1 x ** y = x * (x ** (y - 1))
階乗の場合と同様に、x ** y は x ** (y - 1) がわかれば求めることができます。プログラムは次のようになります。
リスト : 累乗 (1)
fun pow( x, y ) =
if y = 0 then 1.0
else x * pow( x, y - 1 )
再帰定義を使って x ** y を計算しています。手続き型言語では単純な繰り返しで実現できる処理ですが、関数型言語では単純な繰り返しでも再帰定義を使って実現します。
このプログラムは n - 1 回の掛け算をしなくてはいけませんが、式を変形するともっと少ない掛け算の回数で求めることがでます。次の式を見てください。
x ** 4 = (x ** 2) ** 2 -> 2 回 x ** 8 = (x ** 4) ** 2 -> 3 回 x ** 16 = (x ** 8) ** 2 -> 4 回 一般化すると x ** y = (x ** (y / 2)) ** 2; （n は偶数） x ** y = ((x ** (y / 2)) ** 2) * x; （n は奇数）
階乗の計算では n を n - 1 の計算に置き換えていきますが、累乗の場合は y を y / 2 に置き換えていくことができます。y が半分になっていくので減少の度合いが大きくなり、計算回数は少なくて済みます。これを単純にプログラムすると、次のようになります。
リスト : 累乗 (2)
fun pow( x, y ) =
if y = 0 then 1.0
else if y mod 2 = 0 then pow( x, y div 2 ) * pow( x, y div 2 )
else x * pow( x, y div 2 ) * pow( x, y div 2 )
y が偶数の場合でも奇数の場合でも、pow1( x, y div 2 ) を 2 回呼び出していますね。同じ計算を 2 回しているのは無駄ですね。そこで、let を使って局所変数を定義します。次のリストを見てください。
リスト : 累乗 (3)
fun pow( x, y ) =
if y = 0 then 1.0
else
let
val z = pow( x, y div 2 )
val zz = z * z
in
if y mod 2 = 0 then zz else x * zz
end
let で変数 z と zz を定義します。z の値は x ** (y/2) です。これは pow1 を再帰呼び出しすれば簡単に求めることができます。zz の値は z ** 2 になります。あとは、y が偶数であれば、zz をそのまま返し、奇数であれば x * zz を返します。このように、局所変数 z に pow1( x, y div 2 ) の値を求めておくことで、累乗を効率的に計算することができます。
リストを操作する関数は再帰定義を使うと簡単に作ることができます。実は、リスト操作と再帰定義はとても相性が良いのです。まずは、リストの長さを求める関数 my_length を作りましょう。 SML/NJ には length という同等の機能を持つ関数が用意されていますが、再帰定義を使えば簡単に作ることができます。
まず、いちばん簡単な場合を考えます。引数が空リスト nil であれば 0 を返せばいいですね。あとは、リストが空リストになるように分解していけばいいのです。つまり、リスト x の長さを求めるには、リスト x に tl を適用したリストの長さがわかればいい、と考えるのです。それに 1 を足せば、リストの長さを求めることができます。これをプログラムすると、次のようになります。
リスト : リストの長さを求める
fun my_length( x ) =
if null( x ) then 0
else 1 + my_length( tl( x ) )
関数 null( x ) は引数 x が空リストであれば真 (true) を返し、そうでなければ偽 (false) を返します。引数 x が空リストであれば 0 を返します。そうでなければ、引数 x に関数 tl を適用して my_length を再帰呼び出しします。リストに tl を繰り返し適用していくと最後は空リストになります。ここで再帰呼び出しが止まって 0 を返します。そうすると、1 + my_length によって my_length の返り値に 1 を足した値を返していきます。すなわち tl した回数だけ 1 が足されるわけです。
ところで、SML/NJ では格納するデータ型によってリストの型は変化します。もしも、int list と string list で異なる関数が必要だとしたら、とても面倒なことですね。ところが SML/NJ の場合、関数をひとつ定義するだけで、int list にも string list にも対応することができます。このような関数を「多相型関数 (polymorphic function) 」といいます。
多相型関数の極端な例に「恒等関数 (identity function) 」があります。次の例を見てください。
- fun identity( x ) = x; val identity = fn : 'a -> 'a - identity( 10 ); val it = 10 : int - identity( 0.5 ); val it = 0.5 : real - identity( "foo" ); val it = "foo" : string - identity( [1,2,3] ); val it = [1,2,3] : int list
関数 identity は引数をそのまま返す関数です。'a は「型変数」といって、任意のデータ型を表します。identity の型は 'a -> 'a なので、任意の型のデータを受け取り、同じ型を返す関数であることがわかります。したがって、identity は int, real, string, int list など、SML/NJ のデータ型であれば何でも対応することができます。
実際に my_length を定義すると次のように表示されます。
val my_length = fn : 'a list -> int
my_length の場合、任意の型 'a を格納するリストを引数に取り、int を返すことが示されています。つまり、引数が int list でも string list でも、リストであればその長さを返すことができます。このように、my_length は多相型関数として定義されます。SML/NJ の組み込み関数 null, hd, tl も多相型関数です。
それでは実際に試してみましょう。
- my_length( [1,2,3,4,5,6] ); val it = 6 : int - my_length( ["ab", "cd", "ef"] ); val it = 3 : int
正常に動作していますね。SML/NJ は型チェックを厳密に行うプログラミング言語ですが、多相型関数により柔軟なプログラミングが可能になっています。
次はリストを連結する演算子 @ と同じ動作をする関数 append を作ってみましょう。引数としてリスト x と y を渡して、それを連結したリストを返します。
処理手順ですが、簡単な場合から考えていきましょう。まず、リスト x が空リストならば、リスト y を返すだけでいいですね。次に、リスト x に要素が 1 つしかない場合を考えてみます。これは、リスト x に hd を適用して要素を取り出し、それをコンス演算子でリスト y の先頭に追加すればいいでしょう。
それでは、リスト x に要素が複数ある場合を考えてください。リスト x を hd と tl で分解します。そして、tl( x ) と y を連結したリストを求め、そのリストの先頭に hd( x ) を追加すれば x と y を連結することができます。tl( x ) と y の連結は再帰呼び出しで実現することができます。これを図に示すと次のようになります。
┌────────────────────────────┐
│append( [1, 2], [3, 4] ) │
├────────────────────────────┤
│ [ 1, 2 ] │
│ ┬ ─── tl ─┐ │
│ hd ↓ │
│ │ ┌──────────────────────┐│
│ │ │append( [2], [3, 4] ) ││
│ │ ├──────────────────────┤│
│ │ │ [ 2 ] ││
│ │ │ ┬ ─ tl ─┐ ││
│ │ │ hd ↓ ││
│ │ │ │ ┌────────────────┐││
│ │ │ │ │append( [], [3, 4] ) => [3, 4] │││
│ │ │ │ └────────────────┘││
│ │ │ │ │ ││
│ │ │ └→ :: ←─┘ ││
│ │ │ [2, 3, 4] ││
│ │ └─────┼────────────────┘│
│ └──→ :: ←─┘ │
└──────┼─────────────────────┘
↓
[1, 2, 3, 4]
図：append の動作
これをプログラムすると次のようになります。
リスト : リストの結合
fun append( x, y ) =
if null( x ) then y
else hd( x ) :: append( tl( x ), y )
引数 x が空リストであればリスト y をそのまま返します。これが再帰呼び出しの停止条件になります。そうでなければ、tl( x ) を append に渡して再帰呼び出しします。そして、その返り値と hd( x ) をコンス演算子で接続します。これでリストを連結することができます。
実際に append を定義すると、次のように表示されます。
val append = fn : 'a list * 'a list -> 'a list
append も多相型関数になります。簡単な実行例を示します。
- append( [1, 2, 3], [4, 5, 6] ); val it = [1,2,3,4,5,6] : int list - append( ["ab", "cd"], ["ef", "gh"] ); val it = ["ab","cd","ef","gh"] : string list
今度はリストの要素を反転する関数 reverse を作ってみましょう。SML/NJ には rev という同等の機能を持つ関数が用意されていますが、再帰定義で簡単に作ることができます。reverse は引数のリスト x を hd と tl で分解し、tl( x ) を反転させてから hd( x ) を最後尾に追加することで実現できます。次の図を見てください。
[1, 2, 3] [3, 2] @ [1] => [3, 2, 1]
↓ ↑
[2, 3] [3] @ [2] => [3, 2]
↓ ↑
[3] nil @ [3] => [3]
↓ ↑
nil ──┘
図：reverse の動作
これをプログラムすると、次のようになります。
リスト：リストの反転
fun reverse( x ) =
if null( x ) then nil
else reverse( tl( x ) ) @ [hd(x)]
引数 x が空リストの場合は nil を返します。そうでなければ、reverse を再帰呼び出しして tl( x ) を反転し、演算子 @ で反転したリストの最後尾に先頭の要素を追加します。
実際に reverse を定義すると、次のように表示されます。
val reverse = fn : 'a list -> 'a list
reverse も多相型関数になります。簡単な実行例を示します。
- reverse( [1, 2, 3] ); val it = [3,2,1] : int list - reverse( [1, 2, 3, 4, 5, 6, 7, 8, 9] ); val it = [9,8,7,6,5,4,3,2,1] : int list - reverse( ["ab", "cd", "ef"] ); val it = ["ef","cd","ab"] : string list
次はリストからデータを探索する関数 member を作ってみましょう。関数の名前と動作は Common Lisp から拝借しました。member はリストの中にデータがなければ空リスト (nil) を返します。データを見つけた場合は、そのリストの残りを返します。つまり、返り値のリストの先頭要素が見つけたデータになります。
プログラムは次のようになります。
リスト：リストの探索
fun member( x, y ) =
if null( y ) then nil
else if x = hd( y ) then y
else member( x, tl( y ) )
関数 member はリスト y の中から x を探します。これは member を再帰呼び出ししてリストを分解し、リストの先頭要素をチェックしていくことで実現できます。y が空リストの場合は x を見つけることができなかったので nil を返します。これが再帰の停止条件になります。次に、リスト y の先頭の要素 hd( y ) が x と等しいかチェックします。そうであれば、リスト y をそのまま返します。そうでなければ、member を再帰呼び出しして次の要素を調べます。
実際に member を定義すると、次のように表示されます。
val member = fn : ''a * ''a list -> ''a list
''a は ' が 2 個ついていますが、これを「等値型」の型変数といいます。等値型とは、等値演算子 (=, <>) で比較できるデータ型のことです。int, real, string, bool などの基本的なデータ型は等値型です。また、要素が等値型の組やリストも等値型になります。次の例を見てください。
- (1,2) = (1,2); val it = true : bool - (1,2) = (2,1); val it = false : bool - [1,2,3] = [1,2,3]; val it = true : bool - [1,2,3] = [3,2,1]; val it = false : bool
member は多相型関数ですが、データの比較で演算子 = を使っているため、等値型のデータに制限されているのです。それでは、簡単な実行例を示します。
- member( 3, [1,2,3,4,5] ); val it = [3,4,5] : int list - member( 5, [1,2,3,4,5] ); val it = [5] : int list - member( 0, [1,2,3,4,5] ); val it = [] : int list - member( "ab", ["ab", "cd", "ef"] ); val it = ["ab","cd","ef"] : string list - member( "ac", ["ab", "cd", "ef"] ); val it = [] : string list
関数を定義する場合、引数に「パターン (pattern)」を使うことができます。SML/NJ のパターン機能は、論理型言語 Prolog の「パターンマッチング (pattern matching) 」とよく似ています。たとえば、パターンを使って階乗を求める関数 fact を定義すると次のようになります。
リスト : 階乗
fun fact( n ) =
if n = 0 then 1
else n * fact( n - 1 )
(* パターンを利用 *)
fun fact( 0 ) = 1
| fact( n ) = n * fact( n - 1 )
(* ... *) はコメントを表します。SML/NJ の場合、コメントは入れ子になってもかまいません。パターンを使って関数を定義する場合、縦線 | で複数の関数定義をつなげます。このとき、当然ですが関数は同じ名前にしてください。SML/NJ は引数とパターンがマッチングする関数を選択して実行します。
パターンが定数の場合、同じ値の引数とマッチングします。最初の定義はパターンが 0 なので、引数が 0 の場合にマッチングします。これは if n = 0 then 1 と同じ処理です。パターンが変数の場合、どんな値とでもマッチングします。したがって、n が 0 以外の場合は 2 番目の定義と一致します。ここで再帰呼び出しが行われます。このように、if を使わなくてもパターンでプログラムを作ることができます。
パターンを使うときは、関数を定義する順番に気をつけてください。fact の場合、最初に fact( n ) を定義すると、引数が 0 の場合でもマッチングするので、fact( 0 ) が選択されなくなります。引数を特定するパターンから定義するように注意してください。
パターンは定数や変数だけではなく、組やリストにも適用することができます。また、関数の引数だけではなく、val で変数を宣言するときにもパターンを使うことができます。次の例を見てください。
- val (a, b) = (1, 2); val a = 1 : int val b = 2 : int - val ((c, d), e) = ((1, 2), 3); val c = 1 : int val d = 2 : int val e = 3 : int
このように、パターンを使って組の要素を取り出すことができます。型が違うとマッチングに失敗してエラーになります。ご注意ください。
リストもパターンとマッチングすることができます。リストのパターンはコンス演算子 :: を使って表します。たとえば、パターンを使って関数 append を定義すると次のようになります。
リスト：リストの連結 fun append( nil, y ) = y | append( x::xs, y ) = x :: append( xs, y )
最初の定義は、第 1 引数が nil とマッチングします。次の定義の x::xs がパターンを表します。このパターンはリストとマッチングして、先頭の要素が x に、先頭要素を取り除いた残りのリストが xs に束縛されます。このように、関数 hd や tl を使わなくてもリストを分解することができます。
リストを表すパターンは x::xs だけではありません。よく使われるパターンを次に示します。
(1) [x] 要素が 1 つのリストとマッチング (2) [x, y] 要素が 2 つのリストとマッチング (3) x::xs 要素が 1 つ以上あるリストとマッチング (4) x1::x2::xs 要素が 2 つ以上あるリストとマッチング (5) x1::x1::xs エラー
(5) のように、パターンの中に同名の変数を使うことはできません。この場合、x1::x2::xs とマッチングさせてから if で x1 と x2 が等しいかチェックすることになります。また、もっと複雑なリストもパターンで表すことができます。
(1) (x, y)::xs 要素が組のリストとマッチング
ex) [(1, 2), (3, 4), (5, 6)] => x = 1, y = 2, xs = [(3, 4), (5, 6)]
(2) (x::xs)::ys 要素がリストのリスト ('a list list) とマッチング
ex) [[1, 2, 3], [4, 5], [6]] => x = 1, xs = [2, 3], ys = [[4, 5], [6]]
このように、パターンはとても強力な機能です。SML/NJ は型チェックを厳密に行う関数型言語ですが、型推論、多相型関数、パターンなどの機能により、とても柔軟にプログラミングすることができます。
それでは例題としてリストをソート (sort) するプログラムを作ってみましょう。ソートは、ある規則に従ってデータを順番に並べることです。たとえば、データが整数であれば、大きい順かもしくは小さい順に並べます。ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。その中でも「クイックソート (quick sort) 」は高速のアルゴリズムとして有名です。もちろん、SML/NJ でもクイックソートをプログラムすることができます。要素が整数のリストをクイックソートしてみることにしましょう。
クイックソートはある値を基準にして、要素をそれより大きいものと小さいものの 2 つに分割していくことでソートを行います。基準になる値のことを「枢軸」といいます。枢軸は要素の中から適当な値を選んでいいのですが、リストの場合は任意の要素を簡単に選ぶことができません。この場合、いちばん簡単に求めることができる先頭の要素を枢軸とします。
リストを 2 つに分けたら、それらを同様にソートします。これは、再帰を使えば簡単に実現できます。その結果を枢軸を挟んで結合します。これを図に表すと次のようになります。
[5, 3, 7, 6, 9, 8, 1, 2, 4]
5 を枢軸に分割
[3, 1, 2, 4] 5 [7, 6, 9, 8]
3を枢軸に分割 7を枢軸に分割
[1, 2] 3 [4] | 5 | [6] 7 [9, 8]
・・・分割を繰り返していく・・・
図：クイックソート
このようにリストを分割していくと、最後は空リストになります。ここが再帰の停止条件になります。あとは分割したリストを結合していけばいいわけです。プログラムは次のようになります。
リスト：クイックソート
fun quick_sort( nil ) = nil
| quick_sort( x::xs ) =
let
val ( m, n ) = partition( x, xs )
in
quick_sort( m ) @ (x :: quick_sort( n ))
end
最初の定義が空リストの場合で、再帰呼び出しの停止条件になります。次の定義でリストを分割してソートを行います。パターン x::xs でリストを分解し、リストの先頭要素 x を枢軸とします。リストの分割は関数 partition で行います。partition は x を基準にリストを 2 つに分割し、それらのリストを組 (a, b) で返します。リスト a が枢軸よりも小さな要素を集めたもので、リスト b が枢軸以上の要素を集めたものです。
quick_sort では let で局所変数 m と n を定義し、partition を呼び出して返り値をパターンで受け取ります。そして、quick_sort を再帰呼び出しして、リスト m, n をソートします。あとは、その結果を枢軸 x を挟んで結合すればいいわけです。
次はリストを分割する関数 partition を説明します。
リスト：リストの分割
fun partition( _, nil ) = ( nil, nil )
| partition( n, x::xs ) =
let
val ( a, b ) = partition( n, xs )
in
if x < n then ( x::a, b ) else ( a, x::b )
end
最初の定義が空リストの場合です。これが再帰呼び出しの停止条件になります。第 1 引数の アンダーライン ( _ ) は「匿名変数 (anonymous variable) 」です。匿名変数はどの値ともマッチングするワイルドカードとして機能します。ただし、マッチングした値を参照することはできません。値を必要としない引数は匿名変数を使うと便利です。空リストの場合は 組 (nil, nil) を返します。
次の定義でリストを分割します。引数のリストをパターン x::xs で分解し、partition を再帰呼び出ししてリスト xs を 2 つに分割します。返り値は局所変数 (a, b) で受け取ります。あとは、枢軸 n と要素 x を比較して、x が n よりも小さければ x をリスト a に追加して返します。そうでなければ、x をリスト b に追加して返します。これで枢軸 n を基準にしてリストを 2 分割することができます。
それでは、簡単な実行例を示しましょう。
val quick_sort = fn : int list -> int list - quick_sort([5,3,7,6,9,8,1,2,4]); val it = [1,2,3,4,5,6,7,8,9] : int list
正常に動作していますね。ところで、今回のプログラムは要素の比較に演算子 < を使ったため、リストの型は int list になりました。実をいうと、リストの要素を比較する関数を引数として渡すように改良すると、quick_sort を多相型関数として定義することができます。これは「高階関数」のところで詳しく説明します。
相互再帰とは、関数 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( x ) =
let
fun rev1( nil, y ) = y
| rev1( x::xs, y ) = rev1( xs, x::y )
in
rev1( x, nil )
end
関数 rev1 は、リストの先頭要素を引数 y の先頭に追加していきます。したがって、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] )
=> y の値 [4, 3, 2, 1] を返す
=> [4, 3, 2, 1]
=> [4, 3, 2, 1]
=> [4, 3, 2, 1]
=> [4, 3, 2, 1]
このように、引数 y には反転途中の値が格納されていることがわかります。
今度は累算変数を使って、二重再帰を末尾再帰へ変換してみましょう。例題としてフィボナッチ数列を取り上げます。フィボナッチ関数の定義とプログラムを再掲します。
フィボナッチ関数の定義
┌ 1; n = 0
f(n) = ┤ 1; n = 1
└ f(n-1) + f(n-2); n > 1
1, 1, 2, 3, 5, 8, 13 .... という直前の 2 項を足していく数列
リスト : フィボナッチ関数
fun fibonacci( n ) =
if n = 0 orelse n = 1 then 1
else fibonacci( n - 1 ) + fibonacci( n - 2 )
このプログラムは二重再帰になっているので、とても時間がかかります。二重再帰を末尾再帰に変換すると、プログラムを高速に実行することができます。プログラムは次のようになります。
リスト : フィボナッチ関数(末尾再帰)
fun fibonacci( n ) =
let
fun fibo( 0, a1, a2 ) = a1
| fibo( n, a1, a2 ) = fibo( n - 1, a1 + a2, a1 )
in
fibo( n, 1, 0 )
end
累算変数 a1 と a2 の使い方がポイントです。現在のフィボナッチ数を変数 a1 に、ひとつ前の値を変数 a2 に格納しておきます。あとは a1 と a2 を足し算して、新しいフィボナッチ数を計算すればいいわけです。fibo の呼び出しを図に示すと、次のようになります。
fibo( 5, 1, 0 )
fibo( 4, 1, 1 )
fibo( 3, 2, 1 )
fibo( 2, 3, 2 )
fibo( 1, 5, 3 )
fibo( 0, 8, 5 )
=> a1 の値 8 を返す
=> 8
=> 8
=> 8
=> 8
=> 8
二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行できるでしょう。
このように、末尾再帰は実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも末尾再帰でプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、末尾再帰に変換するとプログラムがめちゃくちゃ複雑になってしまう、というアルゴリズムもあります。したがって、とくに問題がなければ、再帰定義をむりやり末尾再帰へ変換する必要はないでしょう。わかりやすいプログラムがいちばんだと思います。