今まで、新しいデータ型を定義する方法として、組と datatype を説明しました。今回は「レコード (record)」を説明します。実をいうと、レコードは SML/NJ の基本的なデータ型の一つで、今まで使ってきた「組」はレコードの特殊な場合なのです。
レコードは中カッコ { } で囲み、要素をカンマで区切ります。要素は次の形式で定義します。
ラベル = 値
ラベルは数字または名前です。"ラベル = 値" を「フィールド」、ラベルを「フィールド名」と呼ぶ場合があります。値の部分に式を書いてもかまいません。式の評価結果がラベルの値になります。次の例を見てください。
- {foo=10, bar=20};
val it = {bar=20,foo=10} : {bar:int, foo:int}
- {baz=100, 5=200};
val it = {5=200,baz=100} : {5:int, baz:int}
- {1=10, 2=20, 3=30};
val it = (10,20,30) : int * int * int
- {1=10, 2=20, 4=40};
val it = {1=10,2=20,4=40} : {1:int, 2:int, 4:int}
レコードの型は {ラベル1 : 型式, ラベル2 : 型式, ...} で表されます。{foo=10, bar=20} の型は {bar:int, foo:int} になります。要素の順番は関係ありません。{bar:int, foo:int} も {foo:int, bar:int} も同じ型になります。SML/NJ は要素を昇順に並べて表示します。
組はラベルが 1 から n までの整数で表されている特別な場合です。したがって、レコード {1=10, 2=20, 3=30} は組 (10, 20, 30) と同じです。{1=10, 2=20, 4=40} は 3 が抜けているので組にはなりません。
SML/NJ の場合、コロン ( : ) を使ってデータ型を指定することができます。次の例を見てください。
- fun square x = x * x; val square = fn : int -> int - fun square1 x : real = x * x; val square1 = fn : real -> real - val a = nil; val a = [] : 'a list - val b = nil : int list; val b = [] : int list
関数 square の型は int -> int になりますが、引数 x の型を指定すると real -> real になります。また、空リスト (nil) の型は 'a list ですが、特定の型を指定することもできます。
レコードの値を参照するには #ラベル を使います。
- val a = {foo=10, bar=20};
val a = {bar=20,foo=10} : {bar:int, foo:int}
- #foo a;
val it = 10 : int
- #bar a ;
val it = 20 : int
レコードに #ラベル を適用すると、ラベルの値を参照することができます。組は番号がラベルのレコードなので #番号 で値を参照できるわけです。
もちろん、レコードでもパターンを使うことができます。次の例を見てください。
- val {foo=x, bar=y} = {foo=100, bar=200};
val y = 200 : int
val x = 100 : int
- val {foo, bar} = {foo=1, bar=2};
val bar = 2 : int
val foo = 1 : int
"ラベル = パターン" とするとラベルの値とパターンがマッチングします。{foo=x, bar=y} は変数 x とラベル foo の値、変数 y とラベル bar の値がマッチングして、x = 100, y = 200 になります。パターンを省略してラベルだけ指定すると、ラベルがパターンの変数になります。{foo, bar} は変数 foo とラベル foo の値がマッチングして foo = 1 になり、変数 bar とラベル bar の値がマッチングして bar = 2 になります。
ただし、ラベルが数字の場合はパターンを省略することができません。次の例を見てください。
- val a = {1=10, bar=20};
val a = {1=10,bar=20} : {1:int, bar:int}
- val {1, bar} = a;
stdIn:23.7-23.13 Error: syntax error: deleting COMMA ID RBRACE
- val {1=z, bar} = a;
val z = 10 : int
val bar = 20 : int
ラベルが数字の場合、パターンの指定を省略するとエラーになります。必ずパターンを指定してください。
レコードのパターンは、フィールドの指定に ... を使うことができます。... はワイルドカードで、不要なフィールドの指定を省略することができます。次の例を見てください。
- datatype foo = Bar of {abc:int, def:int, ghi:int};
datatype foo = Bar of {abc:int, def:int, ghi:int}
- val Bar{abc,...} = Bar{abc=1, def=2, ghi=3};
val abc = 1 : int
datatype で新しい型 foo を作成します。レコードはデータ型の一つなので、datatype の型式に使用することができます。データ構成子 Bar の型式は {abc:int, def:int, ghi:int} になります。このレコードからラベル abc の値を取り出したいとき、Bar {abc, ...} のように ... を指定すると、def と ghi の指定を省略することができます。
ただし、フィールド指定の省略は、レコードの型が特定できる場合にのみ可能です。単純に val {abc, ... } と指定すると、レコードの型を特定できずにエラーになります。ご注意くださいませ。
それでは簡単な例題として、データをカウントするプログラムを作ってみましょう。たとえば、入力データが [ "a", "b", "c", "a", "c" ] であれば、"a", "b", "c" の個数を求めます。この場合、"a" が 2 個、"b" が 1 個、"c" が 2 個になります。
一番簡単な方法は連想リストを使うことです。データとその個数を組にし、それをリストに格納にします。連想リストからデータを探索し、データが見つかればその個数を +1 します。見つからなければ、新しい組を生成して連想リストに追加します。
今回はレコードの例題なので、組ではなくレコードを使いましょう。プログラムは次のようになります。
リスト : データの数え上げ
(* カウンタの定義 *)
datatype 'a counter = Cnt of {data:'a, count:int ref}
(* カウントアップ *)
fun countup(Cnt{count, ...}) = count := !count + 1
(* データの探索 *)
fun find_data(w, nil) = NONE
| find_data(w, (R as Cnt{data, ...})::xs) =
if w = data then SOME R else find_data(w, xs)
(* データの個数を求める *)
fun data_count(nil, result) = result
| data_count(x::xs, result) =
let
val v = find_data(x, result)
in
if isSome v then (countup(valOf v); data_count(xs, result))
else data_count(xs, Cnt{data=x, count=ref 1}::result)
end
最初に datatype で counter を定義します。データ型を限定する必要はないので、'a counter としました。レコードの型は {data:'a, count:int ref} とします。データの個数を書き換えるため、count は参照を使って int ref にします。count の書き換えは関数 countup で行います。
データの探索は関数 find_data で行います。第 1 引数の w が探索するデータ、第 2 引数がレコードを格納しているリスト (連想リスト) です。パターンでレコードの data を取り出し、w と等しいかチェックします。そうであれば、レコード R をoption 型に格納して返します。そうでなければ、find_data を再帰呼び出しして次のレコードを調べます。データが見つからなければ NONE を返します。
関数 data_count はデータの個数を数えて、データと個数を格納した連想リストを返します。第 1 引数が入力データのリストで、第 2 引数の result がレコードを格納する連想リストです。まず、find_data で連想リストからデータ x を探します。関数 isSome で option をチェックし、データがあれば関数 countup で count を +1 します。関数 valOf は option からデータを取り出す関数です。見つからなければ、レコードを生成して result に追加します。
それでは、簡単な実行例を示します。
- data_count(["a", "b", "c", "a", "c"], nil);
val it =
[Cnt {count=ref 2,data="c"},Cnt {count=ref 1,data="b"},
Cnt {count=ref 2,data="a"}] : string counter list
- data_count([1, 2, 3, 2, 3, 4, 3, 4, 5], nil);
val it =
[Cnt {count=ref 1,data=5},Cnt {count=ref 2,data=4},Cnt {count=ref 3,data=3},
Cnt {count=ref 2,data=2},Cnt {count=ref 1,data=1}] : int counter list
正常に動作していますね。ところで、このプログラムはデータの種類が増えると実行速度が遅くなります。実は、データの種類が増えると、データを探索する find_data の処理に時間がかかるのです。find_data は列の先頭から順番に要素を比較してデータを探します。これを「線形探索」といいます。
データ数が少なければ線形探索でも何とかなりますが、データ数が多くなると探索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムが「ハッシュ法」と「二分探索木」です。これらのアルゴリズムは次節以降で取り上げることにします。