お気楽 Standard ML of New Jersey 入門

例外

「例外 (exception)」は主にエラー処理で使われる機能です。「例外＝エラー処理」と考えてもらってもかまいません。Common Lisp には「コンディション (condition)」という例外処理があります。最近は例外処理を持っているプログラミング言語が多くなりました。もちろん、SML/NJ にも例外処理があります。

●例外の定義

SML/NJ にはあらかじめ定義されている例外があります。たとえば、次の例を見てください。

- 4 div 0;

uncaught exception Div [divide by zero]
  raised at: stdIn:10.3-10.6

- tl(tl [1]);

uncaught exception Empty
  raised at: smlnj/init/pervasive.sml:195.19-195.24

-

最初の例は 0 で除算した場合です。例外処理を何も行っていなければ、SML/NJ は処理を中断して uncaught exception と表示します。そして、その後ろに例外の種類を表示します。この場合は divide by zero という例外が発生したことがわかります。次の例は空リスト (nil) に tl を適用した場合です。この場合は Empty という例外が発生します。

なお、例外 Empty が発生したことを、「例外 Empty が送出された」という場合もあります。このドキュメントでは、｢例外を送出する」とか「例外が送出された」と記述することにします。

例外は exception を使って、ユーザが独自に定義することができます。

exception 名前
exception 名前 of 型式

たとえば、exception Foo とすると例外 Foo が定義されます。SML/NJ では、例外の名前を英大文字から始める習慣があります。例外に引数を渡す場合は型式を指定します。たとえば、exception Bar of int * int とすると、例外 Bar に整数を 2 つ渡すことができます。それでは、実際に定義してみましょう。

- exception Foo;
exception Foo
- Foo;
val it = Foo(-) : exn

- exception Bar of int * int;
exception Bar of int * int
- Bar;
val it = fn : int * int -> exn

SML/NJ の場合、例外は exn というデータ型になります。型式を指定すると、Bar は例外を返す関数として定義されます。そして、関数 Bar の返り値は例外 Bar になります。

●例外の送出

例外を送出するには raise を使います。

raise 例外

たとえば、raise Foo とすれば例外 Foo が送出されます。raise Bar( 1, 2 ) とすれば、例外 Bar が送出されます。次の例を見てください。

- fun foo n = if n < 0 then raise Foo else 1;
val foo = fn : int -> int
- foo 1;
val it = 1 : int
- foo ~1;

uncaught exception Foo

- fun bar(a, b) = if a < 0 orelse b < 0 then raise Bar(a, b) else 1;
val bar = fn : int * int -> int
- bar(1, 1);
val it = 1 : int
- bar(1, ~1);

uncaught exception Bar

関数 foo n は、n < 0 の場合に例外 Foo を送出し、それ以外の場合は 1 を返します。関数 bar(a, b) は a < 0 または b < 0 の場合に例外 Bar を送出し、それ以外の場合は 1 を返します。if E then F else G は式 F と G の返り値が同じデータ型でなければいけませんが、式 F が例外を送出する raise なので、式 G の評価結果が if の値になります。

それでは簡単な例題として、階乗を求める関数 fact に引数をチェックする処理を追加してみましょう。次のリストを見てください。

リスト : 階乗

exception Negative

fun fact n =
  let
    fun facti(0, a) = a
    |   facti(n, a) = facti(n - 1, n * a) 
  in
    if n < 0 then raise Negative
    else facti(n, 1)
  end

最初に exception で例外 Nagative を定義します。そして、関数 facti を呼び出す前に引数 n の値をチェックします。n < 0 であれば raise で例外 Nagative を送出します。簡単な実行例を示します。

- fact 10;
val it = 3628800 : int
- fact ~10;

uncaught exception Negative

●例外の捕捉

SML/NJ の場合、送出された例外を「捕捉 (catch)」することで、処理を中断せずに継続することができます。処理をやり直したい場合や特別なエラー処理を行いたい場合、例外を捕捉できると便利です。SML/NJ では、次の式で例外を捕捉することができます。

expr handle pat1 => expr1 | pat2 => expr2 | ... | patN => exprN

例外を捕捉するには handle を使います。式 expr の処理で例外が送出されると、その例外とマッチングするパターンの規則を選択し、対応する式を評価します。そして、その結果が handle の返り値となります。式 expr が正常に終了した場合は、expr の評価結果が handle の返り値になります。

簡単な例を示しましょう。次のリストを見てください。

リスト : 例外の捕捉

exception Foo of int

fun foo n = if n < 0 then raise Foo n else 1  

fun foo1 n = foo n handle
  Foo ~1 => (print "Foo error 1\n"; 0) |
  Foo ~2 => (print "Foo error 2\n"; 0) |
  Foo _  => (print "Foo error 3\n"; 0)

関数 foo は引数 n が負の場合に例外 Foo を送出します。関数 foo1 は foo を呼び出し、例外が送出された場合は handle で捕捉します。例外の引数はパターンマッチングで取り出すことができます。Foo ~1 の場合は "Foo error 1" を表示して 0 を返します。関数 foo の返り値は int なので、例外を捕捉したときに評価する式の返り値も int でなければいけません。ご注意ください。

Foo ~2 の場合は "Foo error 2" を表示して 0 を返します。最後のパターンは匿名変数が使われているので、その他の数値はこの規則とマッチングします。"Foo error 3" を表示して 0 を返します。

それでは、実行してみましょう。

- foo ~1;

uncaught exception Foo

- foo1 2;
val it = 1 : int
- foo1 ~1;
Foo error 1
val it = 0 : int
- foo1 ~2;
Foo error 2
val it = 0 : int
- foo1 ~4;
Foo error 3
val it = 0 : int

foo ~1 をそのまま評価すると例外を送出します。foo1 ~1 を評価すると foo が送出した例外を捕捉して、エラー処理を行ってから 0 を返しています。foo1 ~2 も foo1 ~4 も例外 Foo を捕捉しています。このように、例外を捕捉して処理を続行することができます。

初版 2005 年 5 月 21 日
改訂 2020 年 8 月 9 日

順列と組み合わせ

今回は簡単な例題として、「順列 (permutation)」と「組み合わせ (combination)」を取り上げます。

●順列の生成

異なる n 個の順列の総数は、n の階乗 (n!) だけあります。たとえば、3 つの整数 1, 2, 3 の順列は次に示すように 6 通りあります。

1 2 3,  1 3 2,  2 1 3,  2 3 1,  3 1 2,  3 2 1

順列を生成するプログラムは再帰定義で簡単に作ることができます。[1, 2, 3] の順列を生成する場合、最初に 1 で始まる順列を生成します。これは 1 を取り除いた数字 [2, 3] の順列を生成することで実現できます。次は 2 で始まる順列を生成します。同様に、2 を取り除いた数字 [1, 3] の順列を生成すればいいわけです。[2, 3] や [1, 3] の順列を生成する場合も同じように考えることができます。

プログラムは次のようになります。

リスト : 順列の生成 (1)

(* int list の表示 *)
fun print_intlist xs =
  (app (fn x => (print (Int.toString x); print " ")) xs;
   print "\n")

(* 要素の削除 *)
fun remove(_, nil) = nil
|   remove(x, y::ys) =
  if x = y then remove(x, ys) else y :: remove(x, ys)

(* 順列の生成 *)
fun permutation f n xs =
  let
    fun perm(0, _, a) = f (rev a)
    |   perm(n, xs, a) =
      app (fn x => perm(n - 1, remove(x, xs), x::a)) xs
  in
    perm(n, xs, nil)
  end

関数 permutation f n xs は高階関数で、引数 n が選ぶ要素の個数、引数 xs がリスト、引数 f が生成した順列に適用する関数です。たとえば、順列が数字のリストであれば、int list を表示する関数 print_intlist を渡すことで、生成した順列を表示することができます。実際の処理は局所関数 perm で行います。

perm の引数 n が選ぶ要素の個数、引数 xs がリストです。引数 a は累積変数で、選んだ数字を格納するリストです。n が 0 の場合、順列がひとつ完成しました。関数 rev で a を逆順にしてから関数 f に渡します。選んだ数字は a の先頭に追加していくので、逆順になることに注意してください。

n が 0 でなければ、数字を一つ選んで perm を再帰呼び出しします。数字の選択はリストの先頭から順番に行えばいいので、高階関数 app を使っています。匿名関数でリストの要素 x を受け取り、この中で prem を再帰呼び出しします。n を -1 して、xs から x を削除します。そして、x を a に追加します。これで x を選択したことになります。

関数 remove x ys はリスト ys から x と等しい要素を削除します。高階関数 List.filter を使う場合は次のようになります。

fun remove(x, ys) = List.filter (fn y => x <> y) ys

それでは、実際に試してみましょう。

- permutation;
val it = fn : (''a list -> unit) -> int -> ''a list -> unit

- permutation print_intlist 3 [1,2,3];
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
val it = () : unit

正常に動作していますね。

●順列をリストに格納する

生成した順列をリストに格納して返す場合は、List.foldr を使うと簡単です。プログラムは次のようになります。

リスト : 順列の生成 (2)

fun permutation_list n xs =
  let
    fun perm(0, _, a, b) = rev a :: b
    |   perm(n, xs, a, b) =
      List.foldr (fn(x, c) => perm(n - 1, remove(x, xs), x::a, c)) b xs
  in
    perm(n, xs, nil, nil)
  end

局所関数 perm は permutation の局所関数を改造したもので、生成した順列を第 4 引数 b のリストに格納します。perm は順列を格納したリスト (第 4 引数) をそのまま返します。perm を呼び出す場合、この返り値を第 4 引数に渡すことで、生成した順列を格納していくことができます。

List.foldr の初期値 (第 3 引数) に引数 b を渡すことで、匿名関数の第 2 引数 c に順列を格納するリストを渡します。あとは perm を再帰呼び出しすると、その返り値は次に匿名関数を呼び出すときの引数 c に渡されるので、順列を格納したリストを perm に渡していくことができます。

それでは実行結果を示します。

- permutation_list;;
val it = fn : int -> ''a list -> ''a list list

- permutation_list 3 [1,2,3];
val it = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] : int list list

正常に動作していますね。ところで、permutation と permutation_list は remove を使って要素を削除しているので、関数の型は等値型に制限されます。リストの中から要素を一つ選択する関数 select を定義すると、この制約を外すことができます。興味のある方は問題に挑戦してみてください。

●組み合わせの数

次は組み合わせの数を求めるプログラムを作ってみましょう。ここでは組み合わせの数を \({}_n \mathrm{C}_r\) と表記します。\({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。

\( {}_n \mathrm{C}_r = \dfrac{n \times (n-1) \times (n-2) \times \cdots \times (n - r + 1)}{1 \times 2 \times 3 \times \cdots \times r} = \dfrac{n!}{r! \times (n-r)!} \)

皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で「桁あふれ」を起こす恐れがあります。SML/NJ は Common Lisp のような多倍長整数をサポートしていないので、この公式をそのままプログラムするわけにはいきません。そこで、次の公式を使うことにします。

\( {}_n \mathrm{C}_r = \begin{cases} 1 & if \ r = 0 \\ 1 & if \ r = n \\ \dfrac{{}_n \mathrm{C}_{r-1} \times (n - r + 1)}{r} \quad & if \ r \gt 0 \end{cases} \)

この式は \({}_n \mathrm{C}_r\) と \({}_n \mathrm{C}_{r-1}\) の関係を表しています。あとは階乗と同じように、再帰定義を使って簡単にプログラムできます。次のリストを見てください。

リスト : 組み合わせの数を求める

fun comb(n, r) =
  if n = r orelse r = 0 then 1
  else comb(n, r - 1) * (n - r + 1) div r

とても簡単ですね。ところで、SML/NJ の整数 (int) は 32 bit 処理系で ~1073741824 から 1073741823 までなので、このプログラムでも桁あふれする場合があります。どこまで計算できるか試してみましょう。

- comb(16, 8);
val it = 12870 : int
- comb(18, 9);
val it = 48620 : int
- comb(20, 10);
val it = 184756 : int
- comb(22, 11);
val it = 705432 : int
- comb(24, 12);
val it = 2704156 : int
- comb(26, 13);
val it = 10400600 : int
- comb(28, 14);
val it = 40116600 : int
- comb(30, 15);

uncaught exception overflow

SML/NJ の場合、桁あふれが発生すると例外 overflow が送出されます。桁あふれを起こさないようにするには、モジュール IntInf を使います。SML/NJ はコロン ( : ) を使ってデータ型を指定することができます。

リスト : 組み合わせの数を求める (2)

fun comb1(n, r) =
  if n = r orelse r = 0 then 1 : IntInf.int
  else comb1(n, r - 1) * (n - r + 1) div r  

(* 関数の引数で型指定してもよい *)
fun comb1(n : IntInf.int, r) =
  if n = r orelse r = 0 then 1
  else comb1(n, r - 1) * (n - r + 1) div r

val comb1 = fn : ?.intinf * ?.intinf -> ?.intinf

返り値の整数 1 に : IntInf.int を指定することで、計算を多倍長整数で行うことができます。また、関数の引数で型指定を行ってもかまいません。それでは実行してみましょう。

- comb1(30,15);
val it = 155117520 : ?.intinf
- comb1(50,25);
val it = 126410606437752 : ?.intinf
- comb1(100,50);
val it = 100891344545564193334812497256 : ?.intinf

このように、IntInf モジュールを使って多倍長整数で計算を行うことができます。

●パスカルの三角形

それでは、関数 comb を使って「パスカルの三角形」を作ってみましょう。次の図を見てください。


                          図 : パスカルの三角形

パスカルの三角形は、左側の図のように両側がすべて 1 で、内側の数はその左上と右上の和になっています。これは \((a + b)^n\) を展開したときの各項の係数を表しています。そして、その値は右側の図のように組み合わせの数 \({}_n \mathrm{C}_r\)に対応しています。

きれいな三角形にはなりませんが、パスカルの三角形を表示するプログラムを示します。

リスト : パスカルの三角形

fun print_int n = print(Int.toString(n) ^ " ")

fun pascal x =
  let
    fun pas(n, r) =
      if x < n then ()
      else if n < r then (print "\n"; pas(n + 1, 0))  
      else (print_int(comb(n, r)); pas(n, r + 1))
  in
    pas(0, 0)
  end

手続き型言語では「二重ループ」で簡単にプログラムできるのですが、SML/NJ の while ループはまだ説明していないので、再帰定義でプログラムしました。pas(n, r) で x < n の場合が再帰呼び出しの停止条件です。n < r の場合は三角形の 1 行を表示したので、print "\n" で改行してから pas を再帰呼び出しして次の行を表示します。そうでない場合は、comb(n, r) の値を表示して pas を再帰呼び出しします。

それでは実行結果を示します。

- pascal 10;
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
val it = () : unit

ところで、関数 comb を使わないでパスカルの三角形を出力するプログラムを作ってみるのも面白いと思います。興味のある方は挑戦してみてください。

●組み合わせの生成

最後に「組み合わせ (combination)」を生成するプログラムを作ってみましょう。たとえば、リスト [1, 2, 3, 4, 5] の中から 3 個を選ぶ組み合わせは次のようになります。

1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5
2 3 4, 2 3 5, 2 4 5, 3 4 5

最初に 1 を選択した場合、次は [2, 3, 4, 5] の中から 2 個を選べばいいですね。2 番目に 2 を選択したら、次は [3, 4, 5] の中から 1 個を選べばいいわけです。これで、[1, 2, 3], [1, 2, 4], [1, 2, 5] が生成されます。[2, 3, 4, 5] の中から 2 個選ぶとき、2 を選ばない場合があります。この場合は [3, 4, 5] の中から 2 個を選べばいいわけです。ここで 3 を選ぶと [1, 3, 4], [1, 3, 5] が生成できます。同様に、3 を除いた [4, 5] の中から 2 個をえらぶと [1, 4, 5] を生成することができます。

これで 1 を含む組み合わせを生成したので、次は 1 を含まない組み合わせ、つまり [2, 3, 4, 5] から 3 個を選ぶ組み合わせを生成すればいいわけです。けっきょく、この処理の考え方は次に示す組み合わせの公式と同じです。

\( {}_n \mathrm{C}_r = \begin{cases} 1 & if \ r = 0 \\ 1 & if \ r = n \\ {}_{n-1} \mathrm{C}_{r-1} + {}_{n-1} \mathrm{C}_r \quad & if \ r \gt 0 \end{cases} \)

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

リスト : 組み合わせの生成

fun combination f r xs = 
  let
    fun comb(0, _, a) = f (rev a)
    |   comb(_, nil, _) = ()
    |   comb(r, y::ys, a) = (comb(r - 1, ys, y::a); comb(r, ys, a))
  in
    comb(r, xs, nil)
  end

局所関数 comb は引数 xs のリストから r 個を選ぶ組み合わせを生成します。選んだ数字は引数 a に格納します。r が 0 になったら組み合わせを一つ生成できたので、a を rev で逆順にして関数 f を呼び出します。xs が空リストならば何もしないで unit を返します。この 2 つの条件が再帰呼び出しの停止条件になります。

最後の節は xs が空リストでない場合です。ここで comb を再帰呼び出しします。最初の呼び出しは先頭の要素を選択する場合です。先頭要素を a に追加して、リスト ys の中から r - 1 個を選びます。最後の呼び出しが先頭の要素を選ばない場合です。リスト ys の中から r 個を選びます。

簡単な実行例を示します。

- combination print_intlist 3 [1,2,3,4,5];
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
val it = () : unit

正常に動作していますね。

●組み合わせをリストに格納する

生成した組み合わせをリストに格納して返す場合も簡単です。プログラムは次のようになります。

リスト : 組み合わせの生成 (2)

fun combination_list r xs = 
  let
    fun comb(0, _, a, b) = rev a :: b
    |   comb(_, nil, _, b) = b
    |   comb(r, y::ys, a, b) = comb(r - 1, ys, y::a, comb(r, ys, a, b))
  in
    comb(r, xs, nil, nil)
  end

局所関数 comb は生成した組み合わせを第 4 引数のリストに格納します。comb は組み合わせを格納したリスト (第 4 引数) をそのまま返します。comb を呼び出す場合、この返り値を第 4 引数に渡すことで、生成した組み合わせを格納していくことができます。具体的には、comb を再帰呼び出しするところで、1 回目の呼び出しの返り値を 2 回目の呼び出しの第 4 引数に渡します。これで生成した組み合わせをリストに格納することができます。

それでは実行結果を示します。

val combination_list = fn : int -> 'a list -> 'a list list

- combination_list 3 [1,2,3,4,5];
val it =
  [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],
   [3,4,5]] : int list list

正常に動作していますね。

●問題

次の関数を定義してください。

リスト xs を平坦化する関数 flatten xs

SML/NJ には同様の関数 List.concat が用意されている

マッピングの結果を平坦化する関数 flatmap f xs
リスト xs から要素を一つ選び、その要素と残りの要素を返す関数 select xs

select [1,2,3] ==> [(1,[2,3]), (2,[1,3]), (3,[1,2])]

flatmap と select を使って順列を生成する関数 permutation_list n xs を書き直してください
m 個の整数 (0, 1, 2, ..., m - 1) の「完全順列 (derangement)」を生成する高階関数 derangement f m

完全順列は i 番目の要素が整数 i ではない順列のこと

●解答

リスト : 解答例

fun flatten nil = nil
|   flatten (x::xs) = x @ flatten xs

fun flatmap f nil = nil
|   flatmap f (x::xs) = f x @ flatmap f xs

(* 別解 
fun flatmap f xs = flatten (map f xs)
*)

fun select nil = nil
|   select [x] = [(x, nil)]
|   select (x::xs) = (x, xs) :: map (fn(y, ys) => (y, x::ys)) (select xs)

fun permutation_list1 n xs =
  if n = 0 then [nil]
  else flatmap (fn(y, ys) => map (fn zs => y::zs) (permutation_list1 (n - 1) ys)) (select xs)

fun iota(n, m) =
  if n > m then []
  else n :: iota(n + 1, m)

fun derangement f m =
  let
    fun perm(_, nil, a) = f (rev a)
    |   perm(n, xs, a) =
      app (fn x => if x = n then () else perm(n + 1, remove(x, xs), x::a)) xs
  in
    perm(0, iota(0, m - 1), nil)
  end

- flatten;
val it = fn : 'a list list -> 'a list
- flatten [[1,2,3],[4,5,6],[7,8,9]];
val it = [1,2,3,4,5,6,7,8,9] : int list

- flatmap;
val it = fn : ('a -> 'b list) -> 'a list -> 'b list
- map (fn x => [x,x,x]) [1,2,3,4,5];
val it = [[1,1,1],[2,2,2],[3,3,3],[4,4,4],[5,5,5]] : int list list
- flatmap (fn x => [x,x,x]) [1,2,3,4,5];
val it = [1,1,1,2,2,2,3,3,3,4,4,4,5,5,5] : int list

- select;
val it = fn : 'a list -> ('a * 'a list) list
- select [1,2,3,4];
val it = [(1,[2,3,4]),(2,[1,3,4]),(3,[1,2,4]),(4,[1,2,3])]
  : (int * int list) list

- permutation_list1;
val it = fn : int -> 'a list -> 'a list list
- permutation_list1 3 [1,2,3];
val it = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] : int list list
- permutation_list1 4 [1,2,3,4];
val it =
  [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],[2,1,3,4],
   [2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],[3,1,2,4],[3,1,4,2],
   [3,2,1,4],[3,2,4,1],...] : int list list

- derangement;
val it = fn : (int list -> unit) -> int -> unit
- derangement print_intlist 3;
1 2 0
2 0 1
val it = () : unit
- derangement print_intlist 4
= ;
1 0 3 2
1 2 3 0
1 3 0 2
2 0 3 1
2 3 0 1
2 3 1 0
3 0 1 2
3 2 0 1
3 2 1 0
val it = () : unit

初版 2005 年 5 月 14, 21日
改訂 2020 年 8 月 9 日

配列と参照

SML/NJ は関数型言語なので、関数の引数や let で定義した局所変数の値を書き換えることはできません。ところが、「配列 (array)」と「参照 (reference)」というデータ型に限り、値を書き換えることができます。つまり、手続き型言語のように「副作用」を伴う操作を行うことができるわけです。関数型言語としては不純な機能なのですが、問題によっては配列や参照を使った方が簡単にプログラムできる場合もあります。

●配列

配列を操作する関数はストラクチャ Array に定義されています。配列の生成は関数 array を使います。

Array.array(size, init_value)

array で生成される配列は 1 次元配列です。size は配列の大きさ、init_value は初期値を指定します。簡単な例を示します。

- val a = Array.array(8, 0);
val a = [|0,0,0,0,0,0,0,0|] : int array

- val b = Array.array(8, true);
val b = [|true,true,true,true,true,true,true,true|] : bool array

- val c = Array.array(8, (0, 0));
val c = [|(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0),(0,0)|] : (int * int) array

SML/NJ の場合、配列は [| ... |] で表します。ただし、リストや組と違って配列の生成に [| ... |] を使うことはできません。配列の型はリストのように格納するデータ型によって決まります。int を格納する配列は int array に、bool であれば bool array に、組であれば (int * int) array のようになります。

配列のアクセスは関数 sub と update で行います。

Array.sub(a, n)
Ayyay.update(a, n, data)

関数 sub は第 1 引数に配列、第 2 引数に整数値 (添字 : subscript) を指定します。配列の要素は 0 から数えます。関数 sub をＣ言語で書くと a[n] に相当します。次の例を見てください。

- a;
val it = [|0,0,0,0,0,0,0,0|] : int array
- Array.sub(a, 0);
val it = 0 : int
- Array.sub(a, 7);
val it = 0 : int
- Array.sub(a, 8);

uncaught exception Subscript [subscript out of bounds]

配列 a の大きさは 8 なので、添字の範囲は 0 から 7 になります。範囲外の添字を指定すると例外が送出されます。

配列の値を書き換えるには関数 update を使います。第 1 引数が配列、第 2 引数が添字、第 3 引数が配列に代入するデータです。関数 update をＣ言語で書くと a[n] = data に相当します。次の例を見てください。

- a;
val it = [|0,0,0,0,0,0,0,0|] : int array
- Array.update(a, 0, 10);
val it = () : unit
- Array.update(a, 7, 17);
val it = () : unit
- a;
val it = [|10,0,0,0,0,0,0,17|] : int array

このように、update は配列 a の値を書き換えます。update の返り値は unit です。

●配列の操作関数

ここで、ストラクチャ Array に用意されている関数をいくつか紹介しましょう。配列の大きさは関数 length で求めることができます。

- a;
val it = [|10,0,0,0,0,0,0,17|] : int array
- Array.length a;
val it = 8 : int

関数 fromList はリストを配列に変換します。

- Array.fromList([1,2,3,4,5]);
val it = [|1,2,3,4,5|] : int array

- Array.fromList(["ab","cd","ef","gh"]);
val it = [|"ab","cd","ef","gh"|] : string array

Array には配列用の高階関数も用意されています。

val app : ('a -> unit) -> 'a array -> unit
val foldl : ('a * 'b -> 'b) -> 'b -> 'a array -> 'b
val foldr : ('a * 'b -> 'b) -> 'b -> 'a array -> 'b
val modify : ('a -> 'a) -> 'a array -> unit
val tabulate : int * (int -> 'a) -> 'a array

app, foldl, foldr は今までに説明した高階関数の配列バージョンです。関数 modify は配列の要素に関数を適用し、その結果を配列に代入します。配列の内容が書き換えられることに注意してください。つまり、結果を格納する配列を新しく生成するのではなく、引数の配列に結果を代入するのです。簡単な例を示します。

- val a = Array.fromList [1,2,3,4,5];
val a = [|1,2,3,4,5|] : int array

- Array.modify (fn x => x * x) a;
val it = () : unit
- a;
val it = [|1,4,9,16,25|] : int array

このように、modify は引数 a の配列を直接書き換えています。

関数 tabulate は整数 n と関数 f を受け取り、0 から n - 1 までの値を関数 f に適用して、その結果を格納した配列を生成します。次の例を見てください。

- Array.tabulate(8, fn(x) => x);
val it = [|0,1,2,3,4,5,6,7|] : int array

- Array.tabulate(8, fn(x) => x * 2);
val it = [|0,2,4,6,8,10,12,14|] : int array

ちなみに、tabulate は配列だけではありません。ストラクチャ List にはリストを生成する tabulate が用意されています。

●参照

「参照 (reference)」はデータを間接的に参照する機能です。一般に、変数束縛は変数とデータを直接結び付けます。これに対し、参照は変数とデータを直接結び付けるのではなく、その間にデータを指し示す特別なデータ型を経由します。このデータ型を「参照型」といいます。次の図を見てください。

上図 (A) は通常の変数束縛です。val a = 11 とすると、変数 a に数値 11 が束縛されます。(B) が参照を図示したものです。変数 b には参照型データが束縛され、参照型データが数値 11 を指し示しています。変数 b は参照型データを経由して数値 11 を参照することができます。

SML/NJ で参照型データを生成するには ref を使います。次の例を見てください。

- val b = ref 11;
val b = ref 11 : int ref
- b;
val it = ref 11 : int ref
- val c = ref "foo";
val c = ref "foo" : string ref
- c;
val it = ref "foo" : string ref

ref 11 は数値 11 を指し示す参照型データを生成し、それが変数 b に束縛されます。この場合、データの型は int ref になります。ref "foo" は文字列 "foo" を指し示す string ref を生成し、それが変数 c に束縛されます。今後、参照型データを束縛した変数を「ref 変数」と呼ぶことにします。

参照先のデータを求めるには演算子 ! を使います。ref 変数 b と c に演算子 ! を適用すると、次のようになります。

- !b;
val it = 11 : int
- !c;
val it = "foo" : string

- val ref d = b;
val d = 11 : int
- val ref e = c;
val e = "foo" : string

ref はパターンとしても使えるので、演算子 ! だけではなく、パターンマッチングでも参照先の値を取り出すことができます。

参照型データは参照するデータを変更することができます。次の図を見てください。

上図 (C) は参照するデータを数値 11 から数値 22 に変更しています。すると、ref 変数 b が参照する値は 22 になります。ようするに、ref 変数 b の値を書き換えることと同じ効果が得られるのです。ref 変数の書き換えは演算子 := で行います。次の例を見てください。

- b := 22;
val it = () : unit
- !b;
val it = 22 : int
- c := "bar";
val it = () : unit
- !c;
val it = "bar" : string

b := 22 とすると、ref 変数 b の値は 11 から 22 に書き換えられます。同様に、c := "bar" とすると、ref 変数 c の値は "foo" から "bar" になります。

●繰り返し

今まで繰り返しは再帰定義を使って行いましたが、SML/NJ には簡単な繰り返しを行う while ループが用意されています。

while expr1 do expr2

while は expr1 を評価し、その結果が真の間 expr2 を繰り返し評価します。while の処理を図に示すと次のようになります。

図を見ればおわかりのように while はいたって単純ですが、条件が偽にならないと「無限ループ」に陥ってしまうので注意してください。while はユニットを返します。簡単な例を示しましょう。

リスト : 階乗

fun fact( n ) =
  let
    val i = ref n
    val v = ref 1
  in
    while !i > 0 do (  
      v := !v * !i;
      i := !i - 1
    );
    !v
  end

階乗を求める関数 fact を while を使ってプログラムしました。let で ref 変数 i, v を定義し、その値を書き換えながら階乗 n * (n - 1) * ... * 2 * 1 を計算しています。最後に階乗の値 !v を返します。

●FizzBuzz 問題

次は FizzBuzz 問題を SML/NJ で解いてみましょう。FizzBuzz 問題は 1 から 100 までの値を表示するとき、3 の倍数のときは Fizz を、5 の倍数ときは Buzz を表示するというものです。FizzBuzz 問題の詳細については Fizz Buzz - Wikipedia をお読みください。

プログラムは次のようになります。

リスト : FizzBuzz 問題

fun change_fizzbuzz n =
  if n mod 15 = 0 then "FizzBuzz"
  else if n mod 3 = 0 then "Fizz"
  else if n mod 5 = 0 then "Buzz"
  else Int.toString n

fun fizzbuzz () =
  let
    val n = ref 1
  in
    while !n < 100 do (
      print (change_fizzbuzz (!n));
      print " ";
      n := !n + 1
    )
  end

- fizzbuzz ();
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 
26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz 
Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 
76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz 
val it = () : unit

変数 n を 1 に初期化し、while 文の中で 1 ずつ増やしていきます。この中で関数 change_fizzbuzz を呼び出して数値を文字列に変換します。最初の if 文で、n が 15 の倍数 (3 の倍数でかつ 5 の倍数) かチェックします。そうでなければ、次の else if で n が 3 の倍数かチェックし、次の else if で n が 5 の倍数かチェックします。どの条件も該当しない場合は最後の else 節で n を文字列に変換します。

なお、関数型言語らしく 1 から 100 までのリストを生成して、それをマッピングで Fizz Buzz に変換することもできます。プログラムは次のようになります。

リスト : FizzBuzz 問題 (別解)

fun iota n m =
  if n > m then nil
  else n :: iota (n + 1) m

fun fizzbuzz1 () = map change_fizzbuzz (iota 1 100)

- fizzbuzz1 ();
val it =
  ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13",
   "14","FizzBuzz","16",...] : string list
- app (fn x => (print x; print " ")) (fizzbuzz1 ());
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 
26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz 
Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 
76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz 
val it = () : unit

●パスカルの三角形

もうひとつ簡単な例を示しましょう。順列と組み合わせで作成した「パスカルの三角形」を while ループでプログラムしてみます。

リスト : パスカルの三角形を表示

fun pascal x =
  let
    val n = ref 0
    val r = ref 0
  in
    while !n <= x do (
      r := 0;
      while !r <= !n do (
        print_int( comb( !n, !r ) );  
        r := !r + 1
      );
      print("\n");
      n := !n + 1
    )
  end

ref 変数 n と r を用意し、while で「二重ループ」しています。最初のループで n の値を 0 から x まで増やし、次のループで r の値を 0 から n まで増やしています。while ループで複数の式を評価する場合は複文 (expr1; expr2; ... exprN) を使ってください。

それでは実行してみましょう。

- pascal 10;
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
val it = () : unit

正常に動作していますね。

初版 2005 年 5 月 21 日
改訂 2020 年 8 月 9 日

Functional Programming