Ｃ言語や Pascal が「手続き型言語」と呼ばれるのに対し、ML や Lisp は「関数型言語」と呼ばれています。関数型言語は引数に関数を適用していくことでプログラムを実行します。たとえば、数学の関数を考えてください。
関数 f(x, y) は引数 x と y を与えると値を返します。そして、同じ値の引数を与えれば、結果はいつも同じ値になります。このような性質を「参照の透明性」があるといいます。関数型言語の基本的な考え方は、このような数学の関数と同じです。ようするに、関数型プログラミングには「副作用」がないということです。
ところが、Lisp は完全な関数型言語ではありません。引数以外の変数を定義して、値を代入することができるからです。つまり、変数の値を書き換えることでプログラムを実行する「手続き型言語」の機能もあるわけです。とくに Common Lisp の場合、手続き型言語からいろいろな機能が持ち込まれたため、ほかの関数型言語に比べると不純度の高い関数型言語になっています。
これに対し、純粋な関数型言語では引数や変数の値を書き換えることはできません。純粋な関数型言語には手続き型言語の「代入」という操作がありません。これにより、純粋な関数型言語では副作用がなくなり参照の透明性が成立します。
Ｃ言語などの手続き型言語では、変数を間違った値で書き換えるとプログラムは正常に動作しなくなります。プログラムの規模が大きくなるほど、このような間違い (バグ) を見つけるのは難しくなります。純粋な関数型言語であれば、このようなバグに悩まされることはありません。プログラムが正しく動作するか検証するのも手続き型言語より容易になります。
ML の場合、引数以外の変数を定義することができますが、引数や変数の値を書き換えることはできません。ただし、ML は入出力操作で副作用が存在しますし、値を書き換えることができる「参照型」の変数と「配列」が用意されています。ML は純粋な関数型言語 [*1] ではありませんが、Common Lisp に比べれば純度の高い関数型言語といえるでしょう。
それから、関数型言語の場合、関数はほかのデータと同等に取り扱うことができます。つまり、関数を変数に格納したり、引数として渡すことができるのです。また、値として関数を返すこともできるので、関数を作る関数を定義することができます。
このような関数を「汎関数 (functional)」とか「高階関数 (higher-order function)」と呼びます。ML は Lisp よりも簡単に関数を操作することができます。もちろん、不用になったメモリを自動的に回収する「ガベージコレクション」もあります。
手続き型言語に慣れている方は、代入操作なしでどうやってプログラムを作るのか不思議に思われるかもしれません。たとえば、関数型言語では「再帰定義」を使って繰り返しを行います。複雑な処理でも高階関数を使えば簡単に実現できるようになります。最初は戸惑うかもしれませんが、再帰定義も高階関数も難しいテクニックではありません。ポイントさえつかめば簡単に使いこなすことができます。
関数型言語は手続き型言語とは違う独特の面白さがあります。このページでは SML/NJ で簡単なプログラムを作りながら関数型プログラミングを楽しんでいきたいと思っております。興味のある方は関数型プログラミングの世界に足を踏み入れてみましょう。
それでは、さっそく SML/NJ を使ってみましょう。シェルでコマンド sml を実行すると、対話モード (interactive mode) で SML/NJ を起動することができます。
C>sml Standard ML of New Jersey (32-bit) v110.98 [built: ...] -
$ rlwrap sml Standard ML of New Jersey (64-bit) v110.98 [built: ...] -
- は SML/NJ のプロンプトです。Windows の場合、Ctrl-Z (Ctrl キーを押しながら z を押す) を入力してリターンキーを押すと終了します。Unix 系 OS の場合、Ctrl-D を入力すると終了します。プロンプトのあとに式を入力すると、SML/NJ は式を評価して結果を返します。
- 1 + 2 * 3; val it = 7 : int - 2 - 3; val it = ~1 : int - 1.1 + 2.2; val it = 3.3 : real
対話モードで式を入力する場合、最後にセミコロン ( ; ) を入力してからリターンキーを押します。val は値 (value) の意味で、変数の値を表示するときや変数を宣言するときに使います。
it は対話モードで入力された式の評価結果を受け取る特殊変数です。SML/NJ は式 1 + 2 * 3 の計算結果を変数 it に格納して値を表示します。
結果を見ると、値が 7 でデータの種類が int (整数) であることがわかります。データの種類や種別のことを「データ型」、またはたんに「型」といいます。
SML/NJ で負の整数を表す場合、ダッシュ ( - ) ではなくチルダ ( ~ ) を使います。- は引き算だけなので、-3 * 4 のようなマイナス記号には使えません。~3 * 4 と入力してください。それから、SML/NJ は実数 (浮動小数点数) を使うことができます。1.1 + 2.2 を計算すると、結果が 3.3 で型が real (実数) であることが表示されます。
SML/NJ は型を厳密にチェックするプログラミング言語なので、整数と実数を混在させて計算することはできません。次のようにエラーになります。
- 1 + 2.2;
stdIn:1.2-1.9 Error: operator and operand do not agree [overload - bad instantiation]
operator domain: 'Z[INT] * 'Z[INT]
operand: 'Z[INT] * real
in expression:
1 + 2.2
-
SML/NJ の場合、整数は 10 進数で表しますが、先頭に 0x を付けると 16 進数で表すことができます。整数の範囲は 32 bit 処理系と 64 bit 処理系で異なります。
これらの値はモジュール (標準ライブラリ) Int に minInt, maxInt として定義されています。
- Int.maxInt; val it = SOME 1073741823 : int option - Int.minInt; val it = SOME ~1073741824 : int option
- Int.maxInt; val it = SOME 4611686018427387903 : int option - Int.minInt; val it = SOME ~4611686018427387904 : int option
SML/NJ は数値計算するときにオーバーフローをチェックしますが、モジュール IntInf を用いると多倍長整数で計算するので、オーバーフローは発生しません。32 bit 処理系での簡単な例を示します。
- val a = 1073741823; val a = 1073741823 : int - a + 1; uncaught exception Overflow [overflow] raised at: <file stdIn> - val b : IntInf.int = 1073741823; val b = 1073741823 : IntInf.int - b + 1; val it = 1073741824 : ?.intin
モジュールのアクセス方法やデータ型の指定方法についてはあとで詳しく説明します。
SML/NJ の実数は IEEE754 形式という倍精度浮動小数点数で表されていて、範囲は Real モジュールの minNormalPos と maxFinite で定義されています。それから、モジュール Real に正の無限大を表す posInf, 負の無限大を表す negInf が定義されています。
- Real.minNormalPos; val it = 2.22507385851E~308 : real - Real.maxFinite; val it = 1.79769313486E308 : real - Real.posInf; val it = inf : real - Real.negInf; val it = ~inf : real
ここで、よく使われる算術演算子をまとめておきましょう。
/ は実数の除算で、整数の除算は div になります。SML/NJ は英大文字と英小文字を区別するので、div と mod は小文字で入力してください。それから、数式にはカッコ ( ) を使うことができます。
- 3 * (5 - 2); val it = 9 : int
一つの文字を表すデータ型を文字型 (char) といいます。SML/NJ の場合、文字は基本的に 1 byte (0 - 255) の範囲で、日本語 (漢字やカナなど) を文字型として扱うことはできません。文字は #"a" のように # のあとに二重引用符 " で囲んで表します。" を表す場合はエスケープシーケンスを使います。
- #"a"; val it = #"a" : char - #"\""; val it = #"\"" : char - #"\\"; val it = #"\\" : char
文字と整数の変換には関数 ord, chr を使います。
- ord(#"a"); val it = 97 : int - chr(97); val it = #"a" : char
文字列 (string) は "foo" や "bar" のように二重引用符 ( " ) で囲みます。Ｃ言語と同様に、エスケープ記号 ( \ ) を使うことできます。たとえば、\n が改行で \t がタブになります。
- "foo"; val it = "foo" : string - "bar"; val it = "bar" : string - "foo" ^ "bar"; val it = "foobar" : string
文字列は演算子 ^ で連結することができます。
比較演算子は =, <>, <, >, <=, >= があります。値が等しいかチェックする述語が = で、等しくないかチェックする述語が <> です。簡単な例を示しましょう。
- 1 = 1; val it = true : bool - 1 <> 1; val it = false : bool - 1 <> 2; val it = true : bool - 1 < 2; val it = true : bool - 1 > 2; val it = false : bool - "foo" = "foo"; val it = true : bool - "foo" = "bar"; val it = false : bool
SML/NJ は真・偽を型 bool で表します。true が真で false が偽になります。比較演算子は整数や実数だけではなく文字列にも適用することができます。
SML/NJ の論理演算子は名前が少し変わっています。
簡単な例を示しましょう。
- 1 < 2 andalso 3 < 4; val it = true : bool - 1 < 2 andalso 3 > 4; val it = false : bool - 1 < 2 orelse 3 > 4; val it = true : bool - 1 > 2 orelse 3 < 4; val it = true : bool - 1 > 2 orelse 3 > 4; val it = false : bool
条件分岐は if-then-else を使います。if E then F else G は最初に E を評価して、結果が真 (true) であれば式 F を評価し、偽 (false) であれば式 G を評価します。式 F または式 G の評価結果が if の返り値になります。式 F と G の返り値はどんな型でもかまいませんが、同じ型でなければいけません。型が違うとエラーになります。
簡単な例を示しましょう。
- if 1 < 2 then 3 * 4 else 5 * 6; val it = 12 : int - if 1 > 2 then 3 * 4 else 5 * 6; val it = 30 : int
SML/NJ の場合、if-then-else の else は省略することができません。ご注意ください。
変数 (variable) は val で宣言します。
val 名前 = 式
Lisp などの関数型言語では、変数に値を与えることを「束縛 (binding)」といいます。純粋な関数型言語の場合、束縛された変数は値を書き換えることができません。手続き型言語は代入により変数の値を書き換えることができますが、純粋な関数型言語に代入操作はありません。
名前 (識別子) は、先頭が英大文字か英小文字またはアポストロフィ ( ' ) で、そのあとに英大文字、英小文字、数字、アポストロフィ、アンダースコア ( _ ) が続きます。
SML/NJ は英大文字と英小文字を区別するので、たとえば foo と FOO は異なる名前になります。アポストロフィから始まる名前は「型変数」といって、変数名や関数名に使うことはできません。型変数はあとで詳しく説明します。
SML/NJ の場合、val で宣言された変数や関数の引数は、値を書き換えることはできません。ただし、SML/NJ には「参照」と「配列」というデータ型が用意されていて、これらのデータ型に限り値を書き換えることができます。
簡単な例を示しましょう。
- val a = 10; val a = 10 : int - a; val it = 10 : int - val b = 2.0; val b = 2.0 : real - b; val it = 2.0 : real - val c = "foo"; val c = "foo" : string - c; val it = "foo" : string
対話モードの場合、変数名を入力するとその値が表示されます。
SML/NJ は複数の型を組み合わせて新しい型を定義することができます。SML/NJ の場合、新しい型の定義方法は複数あるのですが、もっとも簡単で重要な方法が「組 (tuple, タプル)」です。組は複数のデータや式をカンマ ( , ) で区切り、カッコ ( ) で囲んで表します。次の例を見てください。
- val a = (1, 2); val a = (1,2) : int * int - val b = (10, 20.5); val b = (10,20.5) : int * real - val c = (1, 2.5, "foo"); val c = (1,2.5,"foo") : int * real * string - val d = (1+2, 3*4); val d = (3,12) : int * int
変数 a の組 (1, 2) は整数を 2 つ持っていて、型は int * int になります。このような型を「積型」といいます。積型は複数の型をアスタリスク ( * ) でつなげて表します。変数 b の組 (10, 20.5) は整数と実数なので int * real になります。変数 c の組 (1, 2.5, "foo") は int * real * string になります。また、最後の例のようにカッコの中に式を書くと、それを評価した値が組の要素になります。
組は入れ子にしてもかまいません。次の例を見てください。
- val a = ((1, 2), 3); val a = ((1,2),3) : (int * int) * int - val b = (1, (2, 3)); val b = (1,(2,3)) : int * (int * int)
変数 a の組は、第 1 要素が int * int の組で、第 2 要素が int です。これを (int * int) * int と表します。変数 b の組は、第 1 要素が int で第 2 要素が int * int の組になります。これを int * (int * int) と表します。どちらの組も 3 つの整数が含まれていますが、型は異なることに注意してください。
組から i 番目の要素を取り出すには、組に #i を適用します。次の例を見てください。
- #1(a); val it = (1,2) : int * int - #2(a); val it = 3 : int - #1(b); val it = 1 : int - #2(b); val it = (2,3) : int * int
組の要素は左側から順番に 1 から数えます。変数 a の値は ((1, 2), 3) なので、#1(a) は (1, 2) になり、#2(a) は 3 になります。もっとも、SML/NJ には「パターン」という便利な機能があり、もっと簡単に要素を取り出すことができます。パターンはあとで詳しく説明します。
もうひとつ、とても重要なデータ型に「リスト (list)」があります。SML/NJ のリストは Lisp のリスト (連結リスト) と同じで、複数のデータを格納することができます。ただし、Lisp のリストとは違って、リストの要素は同じ型でなければいけません。リストの構造を図で表すと次のようになります。
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・│・┼─→│・│・┼─→│・│／│ 終端は／で表す
└┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓
１ ２ ３
図 : リスト内部の構造
リストは貨物列車にたとえるとわかりやすいでしょう。車両に相当するものを「コンスセル (cons cell)」といいます。貨物列車には多数の車両が接続されて運行されるように、リストは複数のコンスセルを接続して構成されます。1 つのコンスセルには、貨物 (データ) を格納する場所と、連結器に相当する場所があります。
上図では、コンスセルを箱で表しています。コンスセルの左側がデータを格納する場所で、右側が次のコンスセルと連結しています。この例では、3 つのコンスセルが接続されています。それから、最後尾のコンスセルには、リストの終わりを示すデータが格納されます。
SML/NJ のリストは、要素をカンマ ( , ) で区切り、角カッコ [ ] で囲んで表します。次の例を見てください。
- val a = [1, 2, 3, 4]; val a = [1,2,3,4] : int list - val b = ["abc", "def", "ghi"]; val b = ["abc","def","ghi"] : string list - val c = [(1, 2), (3, 4), (5, 6)]; val c = [(1,2),(3,4),(5,6)] : (int * int) list - val d = [[1], [2, 3], [4, 5, 6]]; val d = [[1],[2,3],[4,5,6]] : int list list - val e = [1 + 2 + 3, 4 * 5 * 6]; val e = [6,120] : int list
変数 a のリストは要素が int なので型は int list になります。[1] や [2, 3] も型は int list になります。リストに格納された要素の個数を「リストの長さ」といいます。リストの型はリストの長さとは関係なく、格納する要素の型によって決まります。変数 b のリストは要素が文字列なので型は string list になります。
組をリストに入れてもかまいません。変数 c は組 int * int を格納するリストなので、型は (int * int) list になります。このリストに (1, 2, 3) という組を入れることはできません。(1, 2, 3) の型は int * int * int で、int * int とは型が異なるからです。
リストは入れ子にすることができます。変数 d のリストは [1], [2, 3], [4, 5, 6] という int list を格納しています。したがって、型は int list list になります。このリストに [[7]] を入れることはできません。[[7]] の型は int list list になるので、要素の型 int list とは異なるからです。また、最後の例のように角カッコの中に式を書くと、それを評価した値がリストの要素になります。
リストは関数 hd, tl を使って分解し、演算子 :: (コンス演算子) で合成することができます。また、演算子 @ でリストを連結することができます。次の例を見てください。
- a; val it = [1,2,3,4] : int list - hd(a); val it = 1 : int - tl(a); val it = [2,3,4] : int list - val e = 0 :: a; val e = [0,1,2,3,4] : int list - val f = [1,2,3] @ [4,5,6]; val f = [1,2,3,4,5,6] : int list
関数 hd(a) は Lisp の関数 car と同じで、リスト a の先頭要素を取り出します。リスト [1, 2, 3, 4] の先頭要素は 1 なので、hd(a) は 1 を返します。tl(a) は Lisp の関数 cdr と同じで、リスト a から先頭要素を取り除いたリストを返します。tl(a) は [1, 2, 3, 4] から 1 を取り除いた [2, 3, 4] を返します。演算子 :: は Lisp の関数 cons と同じで、リストの先頭にデータを付け加えます。演算子 @ は Lisp の関数 append と同じで、2 つのリストをつないだリストを返します。
hd, tl, コンス演算子の関係を図に表すと次のようになります。
┌──┐
┌─→│ｈｄ│→ １ ────┐
│ └──┘ ↓
│ ┌──┐
[1, 2, 3, 4] ─┤ │：：│→ [1, 2, 3, 4]
│ └──┘
│ ┌──┐ ↑
└─→│ｔｌ│→ [2, 3, 4] ─┘
└──┘
図 : リストの分解と合成
この関係は、リストを操作する関数を作る場合の基本になります。
要素のないリストを「空リスト」といい、SML/NJ では nil または [] で表します。次の例を見てください。
- tl([1]); val it = [] : int list - tl(["abc"]); val it = [] : string list
要素が一つしかないリストに tl を適用すると空リストになります。nil はどのようなリスト型にもあてはまります。最初の例は int list に tl を適用したので、[] を int list と表示しました。2 番目の例のように、string list の空リスト [] は string list と表示されます。
コンス演算子を続ける場合は結合規則に注意してください。次の例を見てください。
1::2::3::nil => (1::(2::(3::nil))) => [1, 2, 3]
このように、コンス演算子は四則演算とは違って「右結合」になります。また、コンス演算子の右辺はリストでなければいけません。1::2 はエラーになります。ご注意くださいませ。
実際のプログラムでは、hd や tl でリストを分解するよりも「パターン」を使った方が簡単です。パターンはあとで詳しく説明します。
関数は fun で定義します。
fun 名前(args, ...) = 式
fun のあとに名前と引数 args を書き、= のあとに引数を含む式を書きます。たとえば、引数を 2 倍する関数 times2 を定義すると次のようになります。
- fun times2(x) = x * 2; val times2 = fn : int -> int - times2(4); val it = 8 : int
関数型言語の場合、関数もデータ型の一つです。fun は関数型のデータを生成し、その値を変数に束縛します。fun で指定した名前が times2 であれば、変数 times2 の値は関数型のデータになります。fn は値が関数であることを表し、型は "引数の型 -> 返り値の型" で表します。この型を見ると、関数 times2 は引数に int をひとつ取り、int を返すことがわかります。
ここで、引数や返り値の型を指定しなくても、SML/NJ が型を決めていることに注意してください。この機能を「型推論」といいます。times2 は引数と整数 2 の乗算を行っているので、引数は int で返り値も int になるはずです。このように SML/NJ が型を推論してくれるので、私達が型を指定しなくてもプログラムすることができます。
複数の引数を持つ関数を定義する場合、SML/NJ では組を使います。次の例を見てください。
- fun f(x, y) = 2 * x + 3 * y; val f = fn : int * int -> int - f(1, 2); val it = 8 : int
関数 f は 2 つの引数 x, y を受け取ります。ここで関数 f の型 int * int -> int を見てください。引数の型が int * int の積型になっていますね。実をいうと、SML/NJ の関数は引数を一つしか受け取ることができません。複数の引数は組にして関数に渡します。つまり、関数呼び出し f(1, 2) は、組 (1, 2) に関数 f を適用するという意味なのです。したがって、引数が一つしかない場合は、次のようにカッコを付けなくても関数定義や関数呼び出しができます。
- fun times2 x = x * 2; val times2 = fn : int -> int - times2 10; val it = 20 : int
組を使えば複数の値を返す関数も簡単に作ることができます。次の例を見てください。
- fun foo(x, y) = = if x = y then (0, 0) = else if x < y then (~1, y - x) = else (1, x - y); val foo = fn : int * int -> int * int - foo(10, 20); val it = (~1,10) : int * int - foo(20, 10); val it = (1,10) : int * int - foo(10, 10); val it = (0,0) : int * int
関数 foo は引数 x と y の差分の絶対値を計算し、符号とその値を返します。行頭の = は継続行を表すプロンプトです。if-then-else は else if でつなぐことができます。x = y ならば (0, 0) を返します。x < y ならば (~1, y - x) を返し、x > y ならば (1, x - y) を返します。このように、組を使って複数の値を返すことができます。
関数の引数は「局所変数」として扱われます。局所変数は「有効範囲 (スコープ)」が決まっています。引数の有効範囲は、関数が定義されている式の中だけです。次の例を見てください。
- val x = 10; val x = 10 : int - val y = 20; val y = 20 : int - fun bar y = x + y; val bar = fn : int -> int - bar 100; val it = 110 : int
局所変数として定義されていない変数は「大域変数」になります。大域変数はどこからでも値を参照することができます。対話モードで変数を定義すると、それらの変数は大域変数になります。最初に定義した変数 x と y は大域変数です。
関数 bar は、引数が y で式は x + y です。関数を呼び出す場合、引数用に新しいメモリを割り当て、そこに与えられた引数の値を束縛します。大域変数 y と引数 y は同じ名前ですが、異なる変数になるのです。そして、局所変数が定義されていれば、その値が参照されます。局所変数が定義されていない場合は、大域変数の値が参照されます。したがって、式の中の y は引数 y を参照し、bar の引数に x がないので、式の中の x は大域変数 x を参照します。よって、bar 100 は 10 + 100 = 110 になります。これを図に示すと次のようになります。
┌───── SML/NJ system ─────┐
│ │
│ 大域変数 y │
│ 大域変数 x ←──────┐ │
│ │ │
│ ┌─ 関数 bar 引数 y ─┐ │ │
│ │ ↑ │ │ │
│ │ ┌──┘ │ │ │
│ │ x + y │ │ │
│ │ └──────┼─┘ │
│ └───────────┘ │
│ │
└──────────────────┘
図 : 大域変数と局所変数
関数 bar を実行するとき、関数 bar の枠が作成されると考えてください。このとき、引数用に新しいメモリが割り当てられ、新しい局所変数 y が作成されるわけです。関数の実行が終了すると枠が壊されて、作成された局所変数も廃棄されます。関数 bar の場合、引数 y が廃棄されるので、対話モードでは大域変数 y を参照することができます。このように、関数の引数は関数定義されている式の中だけ有効なのです。
「再帰定義 (recursive definition)」とは、関数定義の中で自分自身を呼び出すことです。再帰呼び出し (recursive call) ともいいます。関数型言語は、再帰定義を使ってプログラムを作ります。まずは簡単な例を見てみましょう。階乗を計算するプログラムです。
階乗の定義からわかるように、n の階乗を求めるには (n - 1) の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができるのです。次のリストを見てください。
リスト : 階乗 fun fact n = if n = 0 then 1 else n * fact(n - 1)
ファイル fact.sml にプログラムが書かれているとしましょう。対話モードで use "fact.sml"; と入力すると、ファイルをロードしてプログラムがコンパイルされます。SML/NJ を実行するときに、"sml fact.sml" のようにコマンドラインからファイル名を指定してもかまいません。
最後で fact 自身を再帰呼び出ししています。それでは、このプログラムの動作を説明します。次の図を見てください。
Call:1 --> Call:2 --> Call:3 --> Call:4 --> Call:5
n:4 n:3 n:2 n:1 n:0
value 24 <-- value : 6 <-- value : 2 <-- value : 1 <-- value : 1
図 : fact の再帰呼び出し（n:引数の値, value:返り値）
上図は関数 fact 4 の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 n の値は 4 なので n の値を 1 減らして fact を再帰呼び出しします。2 回目の呼び出しでは、引数 n の値は 3 に束縛されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 n の値が違うことに注意してください。
関数の引数は、関数呼び出しが行われるたびに新しいメモリに割り当てられ、そこに値が束縛されます。そして、関数の実行が終了すると、引数用に割り当てられたメモリは解放されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n に割り当てられるメモリが異なっているのです。ここが再帰呼び出しを理解するポイントのひとつです。
プログラムを見ると変数 n はひとつしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact 4 を実行しているときの n は 4 であり、fact 3 を呼び出すときには、新しい変数 n を用意して、そこに 3 を束縛するのです。現在のプログラミング言語では、局所変数はあって当然の機能です。再帰呼び出しを使いこなすためにも、局所変数の有効範囲はきちんと理解しておきましょう。
同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then 節が実行され 1 が返されます。ここで再帰呼び出しが止まります。ここが第 2 のポイントです。
停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、プログラムは正常に動作しません。再帰呼び出しを使う場合は、この停止条件に十分注意してください。慣れないうちは、図を描いてみるのもいいでしょう。
fact 0 は 1 を返して fact 1 に戻ります。fact 1 を実行しているあいだ、引数 n の値は 1 ですね。したがって、fact 1 の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って計算し、最後に fact 4 の値 24 を求めることができるのです。
もうひとつ簡単な数値計算の例を示しましょう。フィボナッチ関数も再帰的に定義される関数です。
フィボナッチ関数も再帰定義を使えば簡単にプログラムできます。
リスト : フィボナッチ関数 fun fibonacci n = if n < 2 then n else fibonacci(n - 1) + fibonacci(n - 2)
fibonacci は fact とは違い、自分自身を 2 回呼び出しています。このことを「二重再帰」といいます。fibonacci の呼び出しをトレースすると下図のようになります。
f(5) ┬ f(4) ┬ f(3) ┬ f(2) ┬ f(1)
│ │ │ │
│ │ │ └ f(0)
│ │ └ f(1)
│ └ f(2) ┬ f(1)
│ │
│ └ f(0)
│
└ f(3) ┬ f(2) ┬ f(1)
│ │
│ └ f(0)
└ f(1)
図 : fibonacci のトレース
同じ値を何回も求めているため、効率はとても悪いのです。もちろん、高速に求める方法があるので、心配しないで下さい。
関数の中で引数以外の局所変数を定義できると便利な場合があります。SML/NJ の場合、let ... in ... end で局所変数を定義することができます。let の構造を示します。
let
val name1 = expr1
val name2 = expr2
...
val nameN = exprN
in
expr
end
let と in の間に宣言を書きます。局所変数は val 宣言で定義します。ここで fun 宣言を使うと、局所的な関数を定義することができます。宣言はいくつでも定義することができます。そして、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 が偶数の場合でも奇数の場合でも、pow(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) です。これは pow を再帰呼び出しすれば簡単に求めることができます。zz の値は z ** 2 になります。あとは、y が偶数であれば、zz をそのまま返し、奇数であれば x * zz を返します。このように、局所変数 z に pow(x, y div 2) の値を求めておくことで、累乗を効率的に計算することができます。
次の関数を定義してください。
問題 9, 10 の関数は「多相型関数」になります。これは次回で詳しく説明します。
- fun square n = n * n;
val square = fn : int -> int
- square 10;
val it = 100 : int
- square 100;
val it = 10000 : int
- fun cube n = n * n * n;
val cube = fn : int -> int
- cube 10;
val it = 1000 : int
- cube 100;
val it = 1000000 : int
- fun sum n =
= if n = 1 then 1
= else n + sum (n - 1);
val sum = fn : int -> int
- sum 10;
val it = 55 : int
- sum 100;
val it = 5050 : int
- sum 1000;
val it = 500500 : int
- fun square_sum n =
= if n = 1 then 1
= else square n + square_sum (n - 1);
val square_sum = fn : int -> int
- square_sum 10;
val it = 385 : int
- square_sum 100;
val it = 338350 : int
- fun cube_sum n =
= if n = 1 then 1
= else cube n + cube_sum (n - 1);
val cube_sum = fn : int -> int
- cube_sum 10;
val it = 3025 : int
- cube_sum 100;
val it = 25502500 : int
- fun half n = n / 2.0;
val half = fn : real -> real
- half 10.0;
val it = 5.0 : real
- fun medium(n, m) = half(n + m);
val medium = fn : real * real -> real
- medium(1.0, 2.0);
val it = 1.5 : real
- medium(1.5, 2.5);
val it = 2.0 : real
- fun square_medium(n, m) = medium(n * n, m * m);
val square_medium = fn : real * real -> real
- square_medium(2.0, 3.0);
val it = 6.5 : real
- square_medium(2.5, 3.5);
val it = 9.25 : real
- fun make_list1 a = [a];
val make_list1 = fn : 'a -> 'a list
- make_list1 1;
val it = [1] : int list
- make_list1 "foo";
val it = ["foo"] : string list
- fun make_list2(a, b) = [a, b];
val make_list2 = fn : 'a * 'a -> 'a list
- make_list2(1, 2);
val it = [1,2] : int list
- make_list2("foo", "bar");
val it = ["foo","bar"] : string list
- fun make_list3(a, b, c) = [a, b, c];
val make_list3 = fn : 'a * 'a * 'a -> 'a list
- make_list3(1, 2, 3);
val it = [1,2,3] : int list
- make_list3("foo", "bar", "baz");
val it = ["foo","bar","baz"] : string list
- fun first xs = hd xs;
val first = fn : 'a list -> 'a
- fun second xs = hd (tl xs);
val second = fn : 'a list -> 'a
- fun third xs = hd (tl (tl xs));
val third = fn : 'a list -> 'a
- first [1,2,3,4,5];
val it = 1 : int
- second [1,2,3,4,5];
val it = 2 : int
- third [1,2,3,4,5];
val it = 3 : int
- third [1,2];
uncaught exception Empty
raised at: smlnj/init/pervasive.sml:193.19-193.24