近代的なプログラミング言語は、ユーザーが既存のデータ型を組み合わせて、新しいデータ型を定義する機能を持っています。SML/NJ の場合、組を使って新しい型を表すことができますが、もうひとつ重要な方法に datatype 宣言があります。
datatype (型変数, ... 型変数) 型の名前 =
データ構成子A of 型式A
| データ構成子B of 型式B
.....
| データ構成子N of 型式N
「型式 (type expression)」とはデータ型を表す式のことで、基本的な型である int, real, string, bool などのほかに、関数型や組を表す積型、list と組み合わせてできる int list や string list などがあります。データ構成子とは型式のデータを表す名前です。データを生成するときやパターンマッチングのときにも使用します。
もっとも簡単な datatype 宣言は、Ｃ言語などの列挙型 (enum) のように使う方法です。次の例を見てください。
- datatype fruit = Apple | Orange | Grape; datatype fruit = Apple | Grape | Orange - Apple; val it = Apple : fruit - Grape; val it = Grape : fruit - Orange; val it = Orange : fruit
SML/NJ の場合、データ構成子は英大文字で始める習慣があります。fruit というデータ型は Apple, Orange, Grape から構成されます。このあと、Apple, Orange, Grape を SML/NJ のプログラムで使うことができます。次のように fruit を組やリストに入れることもできます。
- val a = [Apple, Orange, Grape]; val a = [Apple,Orange,Grape] : fruit list - val b = (Apple, Orange); val b = (Apple,Orange) : fruit * fruit
datatype はＣ言語の共用体と同じ働きをします。たとえば、number というデータ型を定義してみましょう。次の例を見てください。
- datatype number = Int of int | Real of real; datatype number = Int of int | Real of real - Int 10; val it = Int 10 : number - Real 1.1; val it = Real 1.1 : number - [Int 1, Real 1.5, Int 2, Real 2.5]; val it = [Int 1,Real 1.5,Int 2,Real 2.5] : number list
number は数を表すデータ型で、データは整数 (int) または実数 (real) です。Int of int によりデータ構成子 Int の型は int と定義され、Real of real でデータ構成子 Real の型は real と定義されます。
データ型 number の生成はデータ構成子を使います。Int 10 または Real 1.1 で number 型のデータが生成されます。Int( 10 ) や Real( 1.1 ) のようにカッコで囲んでもかまいません。最後の例のように、number 型のデータをリストに格納することができます。このように新しいデータ型 number を定義することで、整数と実数をいっしょにリストに格納することができます。
データ構成子は「パターン」として使うことができます。たとえば、number list の整数の合計値と実数の合計値を求める関数 number_sum を作ってみましょう。次のリストを見てください。
リスト : 整数と実数の合計値を別々に求める
fun number_sum num_list =
let
fun sum(nil, i, r) = (i, r)
| sum(Int x ::xs, i, r) = sum(xs, i + x, r )
| sum(Real x ::xs, i, r) = sum(xs, i, r + x )
in
sum(num_list, 0, 0.0)
end
number_sum は整数と実数の合計を求め、組 (int * real) にして返します。実際の処理は関数 sum で行います。sum の第 2, 3 引数を累算変数として使い、第 2 引数に整数の合計値、第 3 引数に実数の合計値を求めます。Int x ::xs と Real x ::xs がパターンです。リストの先頭の要素が Int の場合、2 番目の定義とマッチングして、x の値は整数になります。要素が Real の場合は 3 番目の定義とマッチングして、x の値は実数になります。
それでは実行例を示します。
val number_sum = fn : number list -> int * real - number_sum( [Int 10, Int 11, Real 2.5, Int 12, Real 3.1, Real 4.2] ); val it = (33,9.8) : int * real
型変数を使うと 'a list のような多相的なデータ型を作ることができます。簡単な例として、SML/NJ に定義されている option 型をみてみましょう。option の定義を示します。
datatype 'a option = NONE | SOME of 'a
型変数は datatype と名前の間に指定します。複数の型変数を使う場合は ('a, 'b, ... 'n) のように、型変数をカッコで囲んでカンマで区切ります。option はデータの有無を表す型です。データが無い場合は NONE を、データが有る場合は SOME を使います。SOME の型式は 'a なので、どのデータ型でも option に格納することができます。次の例を見てください。
- NONE; val it = NONE : 'a option - SOME 10; val it = SOME 10 : int option - SOME "foo"; val it = SOME "foo" : string option
NONE だけではデータ型を定めることができないので、型は 'a option と表示されます。SOME 10 の場合、与えられたデータ型が int なので int option になります。同様に、SOME "foo" の型は string option になります。
たとえば、リストからデータを探索する処理を考えてみましょう。「リストの探索」で作成した関数 member は、データが見つかれば残りのリストを、見つからなければ空リスト (nil) を返すように作りました。見つけたデータをそのまま返さないのは、データが見つからない場合の返り値 (nil) とデータ型を一致させるためです。SML/NJ はデータ型を厳密にチェックするプログラミング言語なので、異なるデータ型を返すことはできないのです。
このような場合、役に立つのが option です。見つけたデータをそのまま返さずに、option に格納して返せばいいわけです。簡単な例として、リストの中から述語を満たす要素を探す関数 find_if を作ってみましょう。SML/NJ には find という同じ機能を持つ関数が用意されていますが、私達でも簡単に作ることができます。ちなみに、関数名は Common Lisp (find-if) から拝借しました。
リスト : リストの探索 fun find_if(_, nil) = NONE | find_if(p, x::xs) = if p x then SOME x else find_if(p, xs)
最初の定義で、データが見つからない場合は NONE を返します。次の定義で、述語 p( x ) が真を返せば SOME x を返します。そうでなければ、find_if を再帰呼び出しして次の要素を調べます。
それでは、簡単な実行例を示します。
val find_if = fn : ('a -> bool) * 'a list -> 'a option
- val a = find_if(fn x => x >= 10, [1, 2, 11, 12, 3, 4]); val a = SOME 11 : int option - val b = find_if(fn x => x >= 10, [1, 2, 3, 4, 5, 6]); val b = NONE : int option - isSome a; val it = true : bool - isSome b; val it = false : bool - getOpt(a, 0); val it = 11 : int - getOpt(b, 0); val it = 0 : int - valOf a; val it = 11 : int - valOf b; uncaught exception Option
データが見つからない場合は NONE を返しますが、リストの要素が int なので NONE のデータ型も int option になります。ここで、option 型を操作する主な関数を紹介しましょう。
val getOpt : 'a option * 'a -> 'a val isSome : 'a option -> bool val valOf : 'a option -> 'a
関数 isSome は option 型のデータの有無をチェックする関数です。データがあれば true を、無ければ false を返します。getOpt は option 型からデータを取り出す関数です。データがあればその値を返し、無ければ第 2 引数を返します。valOf もデータを取り出す関数ですが、データが無い場合は「例外 (exception)」を送出します。例外はあとで詳しく説明します。もちろん、パターンマッチングを使ってデータを取り出すこともできます。
datatype は再帰的なデータ構造も定義することができます。たとえば、連結リスト (linkedlist) は次のように定義できます。
datatype 'a linkedlist = Nil | Cell of 'a * 'a linkedlist
Nil が連結リストの終端を表し、Cell がコンスセルを表します。積型 'a * 'a linkedlist で、最初の要素が格納するデータになり、2 番目の要素が次の Cell を格納するデータになります。これで SML/NJ のリストと同等の多相的なデータ型になります。次の例を見てください。
- datatype 'a linkedlist = Nil | Cell of 'a * 'a linkedlist; datatype 'a linkedlist = Cell of 'a * 'a linkedlist | Nil - val a = Cell( 1, Nil ); val a = Cell (1,Nil) : int linkedlist - val b = Cell( 2, a ); val b = Cell (2,Cell (1,Nil)) : int linkedlist - val c = Cell( 10, Cell( 11, Cell( 12, Nil ) ) ); val c = Cell (10,Cell (11,Cell #)) : int linkedlist
このように、Cell を使って linkedlist を組み立てることができます。ようするに、データ構成子 Cell が list のコンス演算子と同じ働きをしているわけです。実際、SML/NJ の list は次のように定義されています。
datatype 'a list = :: of 'a * 'a list | nil
これで多相的なリスト構造を実現できるのですから、SML/NJ の型システムは柔軟で強力な機能だと思います。
それでは簡単な例題として、「連想リスト (association list : a-list)」を作ってみましょう。連想リストは Lisp でよく用いられるデータ構造で、SML/NJ ではキーとデータの組を要素とするリストで実現できます。データ型で記述すると ('a, 'b) list になり、'a がキーで 'b がデータに対応するデータになります。次の図を見てください。
┌────┬────┬────┬──→ データ
│ │ │ │
連想リスト => [("a", 1), ("b", 2), ("c", 3), ("d", 4)]
│ │ │ │
└────┴────┴────┴──→ キー
図 : 連想リストの構造
上図の場合、文字列 "a", "b", "c", "d" がキーで、整数 1, 2, 3, 4 がデータとなります。一般に、キーは等値型のデータが用いられますが、データは何でもかまいません。SML/NJ では連想リストのことを ListPair といい、連想リストを操作する関数がストラクチャ ListPair に定義されています。
今回は SML/NJ の学習ということで、あえて｢連想リスト」を表すデータ型とその操作関数を作成してみましょう。最初に datatype でデータ型を定義します。
リスト : 連想リストの定義
datatype ('a, 'b) alist = Nil | Cell of 'a * 'b * ('a, 'b) alist
名前は alist にしたので、型は ('a, 'b) alist になります。Nil が空の連想リストを表します。Cell の内部では 'a と 'b を組 ('a * 'b) にする必要はないので、Cell の型式は 'a * 'b * ('a, 'b) list としました。
最初に連想リストを生成する関数を作りましょう。関数名は Common Lisp から拝借しました。次のリストを見てください。
リスト : 連想リストの生成 fun acons(x, y, alist) = Cell(x, y, alist) fun pairlis(nil, _) = Nil | pairlis(_, nil) = Nil | pairlis(x::xs, y::ys) = Cell(x, y, pairlis(xs, ys))
関数 acons はキー x とデータ y と連想リスト alist を受け取り、alist の先頭に x と y を追加します。これは簡単ですね。関数 pairlis は 2 つのリストを受け取り、第 1 引数のリストの要素がキー、第 2 引数のリストの要素がデータとなる連想リストを生成します。引数のリストの長さが違う場合は短い方に合わせます。最初の定義が第 1 引数のリストが空になった場合で、次の定義が第 2 引数のリストが空になった場合です。最後の定義で Cell を生成して x と y を格納します。
次はデータを探索する関数を作ります。関数 assoc は指定したキーと等しいデータを探します。関数 assoc_if は述語が真となるキーを探します。どちらの関数も、見つけたキーとデータを組にして option 型に格納して返します。見つからない場合は NONE を返します。
リスト : 連想リストの探索 fun assoc(_, Nil) = NONE | assoc(x, Cell(a, b, next)) = if x = a then SOME (a, b) else assoc(x, next) fun assoc_if(_, Nil) = NONE | assoc_if(f, Cell(a, b, next)) = if f a then SOME (a, b) else assoc_if(f, next)
どちらの関数もパターンマッチングで Cell 内のデータを取り出しています。a がキーで、b がデータ、next が次の Cell です。連想リストが空 (Nil) の場合は option 型の NONE を返します。assoc は引数 x とキー a を比較して、等しければ SOME (a, b) を返します。assoc_if は f a の評価結果が真であれば SOME (a, b) を返します。
それでは、簡単な実行例を示します。
val acons = fn : 'a * 'b * ('a,'b) alist -> ('a,'b) alist
val pairlis = fn : 'a list * 'b list -> ('a,'b) alist
val assoc = fn : ''a * (''a,'b) alist -> (''a * 'b) option
val assoc_if = fn : ('a -> bool) * ('a,'b) alist -> ('a * 'b) option
- val a = acons(1, 10, Nil); val a = Cell (1,10,Nil) : (int,int) alist - val b = acons(2, 12, a); val b = Cell (2,12,Cell (1,10,Nil)) : (int,int) alist - val c = pairlis([1, 2, 3, 4, 5], [11, 12, 13, 14, 15]); val c = Cell (1,11,Cell (2,12,Cell #)) : (int,int) alist - assoc(4, c); val it = SOME (4,14) : (int * int) option - assoc_if(fn x => x mod 2 = 0, c); val it = SOME (2,12) : (int * int) option
正常に動作していますね。