Functional Programming

リスト操作と多相型関数

●再帰定義によるリスト操作

リストを操作する関数は再帰定義を使うと簡単に作ることができます。実は、リスト操作と再帰定義はとても相性が良いのです。まずは、リストの長さを求める関数 my_length を作りましょう。 SML/NJ には length という同等の機能を持つ関数が用意されていますが、再帰定義を使えば簡単に作ることができます。

まず、いちばん簡単な場合を考えます。引数が空リスト nil であれば 0 を返せばいいですね。あとは、リストが空リストになるように分解していけばいいのです。つまり、リスト xs の長さを求めるには、リスト xs に tl を適用したリストの長さがわかればいい、と考えるのです。それに 1 を足せば、リストの長さを求めることができます。これをプログラムすると、次のようになります。

リスト : リストの長さを求める

fun my_length xs =
  if null xs then 0
  else 1 + my_length (tl xs)  

関数 null xs は引数 xs が空リストであれば真 (true) を返し、そうでなければ偽 (false) を返します。my_length は、引数 xs が空リストであれば 0 を返します。そうでなければ、引数 xs に関数 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 を作ってみましょう。引数としてリスト xs と ys を渡して、それを連結したリストを返します。

処理手順ですが、簡単な場合から考えていきましょう。まず、リスト xs が空リストならば、リスト ys を返すだけでいいですね。次に、リスト xs に要素が 1 つしかない場合を考えてみます。これは、リスト xs に hd を適用して要素を取り出し、それをコンス演算子でリスト ys の先頭に追加すればいいでしょう。

それでは、リスト xs に要素が複数ある場合を考えてください。リスト xs を hd と tl で分解します。そして、tl xs と ys を連結したリストを求め、そのリストの先頭に hd xs を追加すれば xs と ys を連結することができます。tl xs と ys の連結は再帰呼び出しで実現することができます。これを図に示すと次のようになります。

これをプログラムすると次のようになります。

リスト : リストの結合

fun append(xs, ys) =
  if null xs then ys
  else hd xs :: append(tl xs, ys)  

引数 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 は引数のリスト xs を hd と tl で分解し、tl xs を反転させてから hd xs を最後尾に追加することで実現できます。次の図を見てください。

これをプログラムすると、次のようになります。

リスト : リストの反転

fun reverse xs =
  if null xs then nil
  else reverse (tl xs) @ [hd xs]  

引数 xs が空リストの場合は nil を返します。そうでなければ、reverse を再帰呼び出しして tl xs を反転し、演算子 @ で反転したリストの最後尾に先頭の要素を追加します。

実際に 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, ys) =
  if null ys then nil
  else if x = hd ys then ys  
  else member(x, tl ys)

関数 member はリスト ys の中から x を探します。これは member を再帰呼び出ししてリストを分解し、リストの先頭要素をチェックしていくことで実現できます。ys が空リストの場合は x を見つけることができなかったので nil を返します。次に、リスト ys の先頭の要素 hd ys が x と等しいかチェックします。そうであれば、リスト ys をそのまま返します。この 2 つが再帰の停止条件になります。そうでなければ、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, ys) = ys
|   append(x::xs, ys) = x :: append(xs, ys)  

最初の定義は、第 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 を多相型関数として定義することができます。これは「高階関数」のところで詳しく説明します。

●問題

次に示すリスト操作関数をパターンマッチングを使って定義してください。

1. リスト xs の先頭から n 個の要素を取り出す関数 take(xs, n)
2. リストの先頭から n 個の要素を取り除く関数 drop(xs, n)
3. 2 つのリスト xs, ys の要素をタプルにまとめたリストを返す関数 zip(xs, ys)
4. zip の逆変換を行う関数 unzip xs
5. 要素 x を n 個持つリストを生成する関数 make_list(x, n)

●解答

- fun take(nil, _) = nil
= | take(_, 0) = nil
= | take(x::xs, n) = x :: take(xs, n - 1);
val take = fn : 'a list * int -> 'a list
- take([1,2,3,4,5], 3);
val it = [1,2,3] : int list
- take([1,2,3,4,5], 0);
val it = [] : int list
- take([1,2,3,4,5], 5);
val it = [1,2,3,4,5] : int list

- fun drop(nil, _) = nil
= | drop(xs, 0) = xs
= | drop(_::xs, n) = drop(xs, n - 1);
val drop = fn : 'a list * int -> 'a list
- drop([1,2,3,4,5], 0);
val it = [1,2,3,4,5] : int list
- drop([1,2,3,4,5], 3);
val it = [4,5] : int list
- drop([1,2,3,4,5], 5);
val it = [] : int list

- fun zip(nil, _) = nil
= | zip(_, nil) = nil
= | zip(x::xs, y::ys) = (x, y) :: zip(xs, ys);
val zip = fn : 'a list * 'b list -> ('a * 'b) list
- zip([1,2,3],[4,5,6]);
val it = [(1,4),(2,5),(3,6)] : (int * int) list
- zip([1,2,3],[4,5]);
val it = [(1,4),(2,5)] : (int * int) list
- zip([1,2],[4,5,6]);
val it = [(1,4),(2,5)] : (int * int) list

- fun unzip nil = (nil, nil)
= | unzip ((x, y)::zs) = let val (a, b) = unzip zs in (x::a, y::b) end;
val unzip = fn : ('a * 'b) list -> 'a list * 'b list
- unzip [(1,2),(3,4),(5,6)];
val it = ([1,3,5],[2,4,6]) : int list * int list

- fun make_list(_, 0) = nil
= | make_list(x, n) = x :: make_list(x, n - 1);
val make_list = fn : 'a * int -> 'a list
- make_list(1, 10);
val it = [1,1,1,1,1,1,1,1,1,1] : int list
- make_list("foo", 3);
val it = ["foo","foo","foo"] : string list

相互再帰と末尾再帰

●相互再帰

相互再帰とは、関数 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