近代的なプログラミング言語は、ユーザーが既存のデータ型を組み合わせて、新しいデータ型を定義する機能を備えています。OCaml の場合、組を使って新しい型を表すことができますが、このほかに「ヴァリアント (variant)」と「レコード (record)」というデータ構造を定義する方法があります。
最初にヴァリアントから説明します。ヴァリアントはＣ言語の共用体とよく似ているデータ構造です。OCaml の場合、新しいデータ型を定義するときは type 宣言を使います。ヴァリアントを定義する構文を次に示します。
type (型変数, ... 型変数) 型の名前 = データ構成子A of 型式A | データ構成子B of 型式B ... | データ構成子N of 型式N
「型式 (type expression)」とはデータ型を表す式のことで、基本的なデータ型である int, float, string, bool などのほかに、関数型や組を表す積型、list と組み合わせてできる int list や string list などがあります。データ構成子 (コンストラクタ) とは型式のデータを表す名前です。OCaml の場合、コンストラクタ名は英大文字から始めます。コンストラクタはデータを生成するときやパターンマッチングのときに使用します。
なお、異なるバリアント型で同名のコンストラクタを定義すると、後から定義したコンストラクタが有効になり、前に定義したコンストラクタは隠蔽されます。たとえば、ヴァリアント foo でコンストラクタ Baz を定義します。その後でバリアント bar でコンストラクタ Baz を定義すると、Baz で生成したデータ型は bar になります。Baz で foo のデータ型は生成できません。ご注意ください。
もっとも簡単なヴァリアントは、Ｃ言語などの列挙型 (enum) のように使う方法です。次の例を見てください。
# type fruit = Apple | Orange | Grape;; type fruit = Apple | Orange | Grape # Apple;; - : fruit = Apple # Grape;; - : fruit = Grape # Orange;; - : fruit = Orange
fruit というデータ型は Apple, Orange, Grape から構成されます。このあと、Apple, Orange, Grape を OCaml のプログラムで使うことができます。次のように fruit を組やリストに入れることもできます。
# let a = [Apple; Orange; Grape];; val a : fruit list = [Apple; Orange; Grape] # let b = (Apple, Orange);; val b : fruit * fruit = (Apple, Orange)
また、ヴァリアントはＣ言語の共用体とよく似た働きをします。たとえば、number というデータ型を定義してみましょう。次の例を見てください。
# type number = Int of int | Float of float;; type number = Int of int | Float of float # Int 10;; - : number = Int 10 # Float 1.1;; - : number = Float 1.1 # [Int 1; Float 1.5; Int 2; Float 2.5];; - : number list = [Int 1; Float 1.5; Int 2; Float 2.5]
number は数を表すデータ型で、データは整数 (int) または実数 (float) です。Int of int によりコンストラクタ Int の型は int と定義され、Float of float でコンストラクタ Float の型は float と定義されます。
データ型 number の生成はコンストラクタを使います。Int 10 または Float 1.1 で number 型のデータが生成されます。Int (10) や Float (1.1) のようにカッコで囲んでもかまいません。最後の例のように、number 型のデータをリストに格納することができます。このように新しいデータ型 number を定義することで、整数と実数をいっしょにリストに格納することができます。
コンストラクタは「パターン」として使うことができます。たとえば、number list の整数と実数の合計値を別々に求める関数 number_sum を作ってみましょう。次のリストを見てください。
リスト 1 : 整数と実数の合計値を別々に求める
let number_sum xs =
let rec sum xs a b =
match xs with
[] -> (a, b)
| Int y :: ys -> sum xs (a + y) b
| Float y :: ys -> sum xs a (b +. y)
in
sum xs 0 0.0
number_sum は整数と実数の合計を求め、組 (int * float) にして返します。実際の処理は局所関数 sum で行います。sum の第 2, 3 引数を累積変数として使い、第 2 引数に整数の合計値、第 3 引数に実数の合計値を求めます。Int y :: ys と Float y :: ys がパターンです。リストの先頭の要素が Int の場合、2 番目の定義とマッチングして、y の値は整数になります。要素が Float の場合は 3 番目の定義とマッチングして、y の値は実数になります。
それでは実行例を示します。
val number_sum = number list -> int * float = <fun>
# number_sum [Int 10; Int 11; Real 2.5; Int 12; Real 3.1; Real 4.2];; - : int * float = (33, 9.8)
型変数を使うと 'a list のような多相的なデータ型を作ることができます。簡単な例として、OCaml に定義されている option 型をみてみましょう。option の定義を示します。
type 'a option = None | Some of 'a
型変数は type と名前の間に指定します。複数の型変数を使う場合は ('a, 'b, ... 'n) のように、型変数をカッコで囲んでカンマで区切ります。option はデータの有無を表す型です。データが無い場合は None を、データが有る場合は Some を使います。Some の型式は 'a なので、どのデータ型でも option に格納することができます。次の例を見てください。
# None;; - : 'a option = None # Some 10;; - : int option = Some 10 # Some "foo";; - : string option = Some "foo"
None だけではデータ型を定めることができないので、型は 'a option と表示されます。Some 10 の場合、与えられたデータ型が int なので int option になります。同様に、Some "foo" の型は string option になります。
たとえば、リストからデータを探索する処理を考えてみましょう。「リストの探索」で作成した関数 member は、データが見つかれば残りのリストを、見つからなければ空リストを返すように作りました。見つけたデータをそのまま返さないのは、データが見つからない場合の返り値である空リストとデータ型を一致させるためです。
OCaml はデータ型を厳密にチェックするプログラミング言語なので、異なるデータ型を返すことはできません。このような場合、役に立つのが option です。見つけたデータをそのまま返さずに、option に格納して返せばいいわけです。
簡単な例として、リストの中から述語を満たす要素を探す関数 find_if を作ってみましょう。OCaml には List.find という同じ機能を持つ関数が用意されていますが、私達でも簡単に作ることができます。ちなみに、関数名は Common Lisp から拝借しました。
リスト 2 : リストの探索 let rec find_if f = function [] -> None | x :: xs -> if f x then Some x else find_if f xs
最初の節で、データが見つからない場合は None を返します。次の節で、述語 f x が真を返せば Some x を返します。そうでなければ、find_if を再帰呼び出しして次の要素を調べます。
それでは、簡単な実行例を示します。
val find_if : ('a -> bool) -> 'a list -> 'a option
# find_if (fun x -> x >= 10) [1; 2; 11; 12; 3; 4];; - : int option = Some 11 # find_if (fun x -> x >= 10) [1; 2; 3; 4; 5; 6];; - : int option = None
データが見つからない場合は None を返しますが、リストの要素が int なので None のデータ型も int option になります。なお、option の値はパターンマッチングを使って取り出すことができます。
ヴァリアントは再帰的なデータ構造も定義することができます。たとえば、連結リスト (linkedlist) は次のように定義することができます。
type 'a linkedlist = Nil | Cell of 'a * 'a linkedlist
Nil が連結リストの終端を表し、Cell がコンスセルを表します。積型 'a * 'a linkedlist で、最初の要素が格納するデータになり、2 番目の要素が次の Cell を格納するデータになります。これで Ocaml のリストと同等の多相的なデータ型になります。次の例を見てください。
# type 'a linkedlist = Nil | Cell of 'a * 'a linkedlist;; type 'a linkedlist = Nil | Cell of 'a * 'a linkedlist # let a = Cell (1, Nil);; val a : int linkedlist = Cell (1, Nil) # let b = Cell (2, a);; val b : int linkedlist = Cell (2, Cell (1, Nil)) # let c = Cell (10, Cell (11, Cell (12, Nil)));; val c : int linkedlist = Cell (10, Cell (11, Cell (12, Nil)))
このように、Cell を使って linkedlist を組み立てることができます。ようするに、コンストラクタ Cell が list のコンス演算子と同じ働きをしているわけです。実際、Ocaml の list は次のように定義されています。
type 'a list = [] | :: of 'a * 'a list
これで多相的なリスト構造を実現できるのですから、OCaml の型システムは柔軟で強力な機能だと思います。
それでは簡単な例題として、「連想リスト (association list : a-list)」を作ってみましょう。前回簡単に説明しましたが、連想リストは組 (key, data) を要素としたリストです。OCaml には連想リストを操作する関数が List モジュールに用意されています。今回は OCaml の学習ということで、あえて｢連想リスト」を表すデータ型とその操作関数を作成してみましょう。
最初にヴァリアントでデータ型を定義します。
リスト 3 : 連想リストの定義
type ('a, 'b) alist = ANil | ACell of 'a * 'b * ('a, 'b) alist
名前は alist にしたので、型は ('a, 'b) alist になります。'a がキーで 'b がデータに対応する型になります。ANil が空の連想リストを表します。ACell の内部では 'a と 'b を組 ('a * 'b) にする必要はないので、ACell の型式は 'a * 'b * ('a, 'b) list としました。
次に連想リストを生成する関数を作りましょう。関数名は Common Lisp から拝借しました。次のリストを見てください。
リスト 4 : 連想リストの生成
let acons x y ls = ACell (x, y, ls)
let rec pairlis xs ys =
match (xs, ys) with
(([], _) | (_, [])) -> ANil
| (x1::xs1, y1::ys1) -> ACell (x1, y1, (pairlis xs1 ys1))
関数 acons はキー x とデータ y と連想リスト ls を受け取り、ls の先頭に x と y を追加します。関数 pairlis は 2 つのリストを受け取り、第 1 引数のリストの要素がキー、第 2 引数のリストの要素がデータとなる連想リストを生成します。引数のリストの長さが違う場合は短い方に合わせます。
最初の節がどちらかのリストが空になった場合です。複数のパターンを | でつなぐパターンを「or パターン」といいます。パターンのどれかがマッチングに成功すれば、その節を選択して評価します。最後の節で ACell を生成して xs の要素 x1 と ys の要素 y1 を格納します。
次はデータを探索する関数を作ります。関数 assoc は指定したキーと等しいデータを探します。関数 assoc_if は述語が真となるキーを探します。どちらの関数も、データを option に格納して返します。見つからない場合は None を返します。
リスト 5 : 連想リストの探索 let rec assoc key = function ANil -> None | ACell (x, y, rest) -> if x = key then Some y else assoc key rest let rec assoc_if f = function ANil -> None | ACell (x, y, rest) -> if f x then Some y else assoc_if f rest
どちらの関数もパターンマッチングで ACell 内のデータを取り出しています。x がキーで、y がデータ、rest が次の ACell です。連想リストが空 (ANil) の場合は None を返します。assoc は引数 x とキー a を比較して、等しければ Some b を返します。assoc_if は f x の評価結果が真であれば Some b を返します。
それでは、簡単な実行例を示します。
val acons : 'a -> 'b -> ('a, 'b) alist -> ('a, 'b) alist = <fun>
val pairlis : 'a list -> 'b list -> ('a, 'b) alist = <fun>
val assoc : 'a -> ('a, 'b) alist -> 'b option = <fun>
val assoc_if : ('a -> bool) -> ('a, 'b) alist -> 'b option = <fun>
# let a = acons 1 10 ANil;; val a : (int, int) alist = ACell (1, 10, ANil) # let b = acons 2 12 a;; val b : (int, int) alist = ACell (2, 12, ACell (1, 10, ANil)) # let c = pairlis [1; 2; 3; 4; 5] [11; 12; 13; 14; 15];; val c : (int,int) alist = ... 省略 ... # assoc 4 c;; - : int option = Some 14 # assoc_if (fun x -> x mod 2 = 0) c;; ^ : int option = Some 12
正常に動作していますね。
次は「レコード (record)」について説明します。レコードはＣ言語の構造体と同じようなデータ構造です。レコードは type 宣言で次のように定義します。
type (型引数, ...) 型名 = {
フィールド名1 : 型1; フィールド名2 : 型2; ... ; フィールド名n : 型n
}
type 宣言の後ろに型名を指定し、その後ろに中カッコ { } で本体を定義します。要素は "フィールド名 : 型" の形式で指定してカンマで区切ります。なお、異なるレコード型で同じフィールド名を使用することはできません。フィールド名が重複している場合、あとから定義したレコードが有効になり、その前に定義したレコードは使うことができなくなります。ご注意ください。
レコードは次の形式で生成します。
{ フィールド名1 = 式1; フィールド名2 = 式2; ... ; フィールド名n = 式n }
式の評価結果がフィールドの値になります。簡単な例を示しましょう。
# type foo = {bar : int; baz : float};;
type foo = { bar : int; baz : float; }
# let a = {bar = 10; baz = 1.23};;
val a : foo = {bar = 10; baz = 1.23}
# a.bar;;
- : int = 10
# a.baz;;
- : float = 1.23
フィールドの値はパターンマッチングで取り出すこともできますが、"レコード + ドット ( . ) + フィールド名" の形式で取り出すこともできます。
OCaml はフィールドの値を変更した新しいレコードを生成することができます。次の例を見てください。
# let b = {a with baz = 123.4};;
val b : foo = {bar = 10; baz = 123.4}
# a;;
val a : foo = {bar = 10; baz = 1.23}
{式0 with フィールド名 = 式; ... } という形式で、式0 で得られるレコードのフィールドの値を、指定した式の評価値に変更した新しいレコードを生成します。なお、元のレコードの値を書き換えることはありません。
もちろん、レコードでもパターンマッチングを使うことができます。次の例を見てください。
# let {bar = x; baz = y} = a;;
val x : int = 10
val y : float = 1.23
# let {baz = z} = a;;
val z = 1.23
"フィールド = パターン" とするとフィールドの値とパターンを照合します。{bar = x; baz = y} は変数 x とフィールド bar の値、変数 y とフィールド bar の値がマッチングして、x = 10, y = 1.23 になります。また、レコードのパターンマッチングは、必要なフィールドだけを指定することができます。フィールド名からレコードの型が分かるので、すべてのフィールドを指定する必要はありません。
レコードは型変数を使って多相的なデータ構造を定義することができます。たとえば、キーとデータの組を表すレコードは次のように定義することができます。
# type ('a, 'b) pair = {key : 'a; data : 'b};;
type ('a, 'b) pair = { key : 'a; data : 'b; }
キー (key) の型を 'a で、データ (data) の型を 'b で表しています。
簡単な例題として、pair を使って連想リストを作ってみましょう。レコードはヴァリアントと組み合わせることができます。次のリストを見てください。
リスト 6 : 連想リストの定義
type ('a, 'b) alist = ANil | ACell of ('a, 'b) pair * ('a, 'b) alist
ACell の型は ('a, 'b) pair * ('a, 'b) alist になります。
連想リストを生成する関数 acons と pairlis は次のようになります。
リスト 7 : 連想リストの生成
let acons x y xs = ACell ({key = x; data = y}, xs)
let rec pairlis xs ys =
match (xs, ys) with
(([], _) | (_, [])) -> ANil
| (x1::xs1, y1::ys1) -> ACell ({key = x1; data = y1}, (pairlis xs1 ys1))
どちらの関数もキーとデータをレコードに格納するだけです。
データを探索する関数 assoc と assoc_if は次のようになります。
リスト 8 : 連想リストの探索
let rec assoc key = function
ANil -> None
| ACell ({key = x; data = y}, rest) -> if x = key then Some y else assoc key rest
let rec assoc_if f = function
ANil -> None
| ACell ({key = x; data = y}, rest) -> if f x then Some y else assoc_if f rest
どちらの関数もパターンマッチングでレコードから値を取り出します。レコードはフィールドに名前が付いているので、組と違ってデータの順番を気にする必要はなく、わかりやすいプログラムになると思います。
それでは、簡単な実行例を示します。
val acons : 'a -> 'b -> ('a, 'b) alist -> ('a, 'b) alist = <fun>
val pairlis : 'a list -> 'b list -> ('a, 'b) alist = <fun>
val assoc : 'a -> ('a, 'b) alist -> 'b option = <fun>
val assoc_if : ('a -> bool) -> ('a, 'b) alist -> 'b option = <fun>
# let a = acons 1 10 ANil;;
val a : (int, int) alist = ACell ({key = 1; data = 10}, ANil)
# let b = acons 2 12 a;;
val b : (int, int) alist =
ACell ({key = 2; data = 12}, ACell ({key = 1; key = 10}, ANil))
# let c = pairlis [1; 2; 3; 4; 5] [11; 12; 13; 14; 15];;
val c : (int,int) alist = ... 省略 ...
# assoc 4 c;;
- : int option = Some 14
# assoc_if (fun x -> x mod 2 = 0) c;;
^ : int option = Some 12
正常に動作していますね。
逆ポーランド記法で書かれた数式を計算するプログラムを作ってください。数式はリストで表すものとにします。リストの要素は次のように定義します。
type item = Add | Sub | Mul | Div | N of float
演算子は Add (+.), Sub (-.), Mul (*.), Div (/.) で、数値は実数 (float) だけとします。
逆ポーランド記法について簡単に説明します。私達が普通に式を書く場合、1 + 2 のように演算子を真ん中に置きます。この書き方を「中置記法」といいます。このほかに、「前置記法」と「後置記法」という書き方があります。前置記法は演算子を前に置く書き方で、ポーランド記法 (Polish Notation) と呼ばれることもあります。たとえば、1 + 2 であれば + 1 2 と書きます。数式にカッコをつけてみると (+ 1 2) となり、Lisp / Scheme のプログラムになります。
後置記法は演算子を後ろに置く書き方で、逆ポーランド記法 (RPN : Reverse Polish Notation) と呼ばれることもあります。1 + 2 であれば 1 2 + のように書きます。逆ポーランド記法の利点は、計算する順番に演算子が現れるため、カッコが不要になることです。たとえば、1 と 2 の和と 3 と 4 の和との積という数式を表してみましょう。
中置記法 : (1 + 2) * (3 + 4) 後置記法 : 1 2 + 3 4 + *
逆ポーランド記法は、日本語の読み方とまったく同じです。1 2 + で 1 と 2 の和を求め、3 4 + で 3 と 4 を求め、最後に 2 つの結果を掛け算して答えが求まります。
val rpn : rpn list -> float = <fun>
# rpn [N 1.0; N 2.0; N 3.0; Add; Add];; - : float = 6. # rpn [N 1.; N 2.; Add; N 3.; N 4.; Add; Mul];; - : float = 21. # rpn [N 1.; N 2.; Add; N 3.; N 4.; Sub; Mul];; - : float = -3. # rpn [N 1.; N 2.; Add; N 3.; N 4.; Add; N 5.; N 6.; Add; Mul; Mul];; - : float = 231.
逆ポーランド記法の数式はスタックを使うと簡単に計算することができます。アルゴリズムは次のようになります。
1. 数値はスタックに追加する。 2. 演算子であればスタックから 2 つ数値を取り出し、演算結果をスタックに追加する。 3. 最後にスタックに残った値が答えになる。
たったこれだけの規則で数式を計算することができます。それでは、実際に 1 2 + 3 4 + * を試してみましょう。次の表を見てください。
| 数式 | 操作 | スタック |
|---|---|---|
| 1 | PUSH | ( 1 ) |
| 2 | PUSH | ( 2 1 ) |
| + | POP (2) | ( 1 ) |
| POP (1) | ( ) | |
| 1+2=3 | ( ) | |
| PUSH | ( 3 ) | |
| 3 | PUSH | ( 3 3 ) |
| 4 | PUSH | ( 4 3 3 ) |
| + | POP (4) | ( 3 3 ) |
| POP (3) | ( 3 ) | |
| 3+4=7 | ( 3 ) | |
| PUSH | ( 7 3 ) | |
| * | POP (7) | ( 3 ) |
| POP (3) | ( ) | |
| 3*7=21 | ( ) | |
| PUSH | ( 21 ) |
スタックはリスト ( ) で表します。最初の 1 と 2 は数値なのでスタックにプッシュします。次は演算子 + なので、スタックからデータを取り出して 1 + 2 を計算します。そして、計算結果 3 をスタックにプッシュします。次に、3 と 4 は数値なのでスタックにプッシュします。その次は演算子 + なので同じように処理して、計算結果 7 をスタックにプッシュします。
スタックの中身は ( 7 3 ) となり、最初の計算結果 3 と次に計算した結果 7 がスタックに格納されています。この状態で最後の * を処理します。7 と 3 を取り出すとスタックは空の状態になります。そして、3 * 7 を計算して 21 をスタックにプッシュします。これで計算は終了です。スタックに残っている値 21 が計算結果となります。
このように、スタックを使うことで逆ポーランド記法で書かれた数式を簡単に計算することができます。実は数式だけではなく、スタックを用いてプログラムを実行することもできます。プログラミング言語 Forth は「数値」と「ワード」という 2 種類のデータしかありません。ワードには +, -, *, / などの演算子のほかに、いろいろな処理が定義されています。もちろん、ユーザが新しいワードを定義することもできます。
Forth の動作は、数値であればスタックにプッシュして、ワードであればそれを実行する、というシンプルなものです。これでプログラミングができるのですから、とてもユニークな言語ですね。
プログラムは次のようになります。
リスト : 数式の計算 (後置記法)
type rpn = Add | Sub | Mul | Div | N of float
let rpn_add = function
y::x::zs -> (x +. y)::zs
| _ -> [nan]
let rpn_sub = function
y::x::zs -> (x -. y)::zs
| _ -> [nan]
let rpn_mul = function
y::x::zs -> (x *. y)::zs
| _ -> [nan]
let rpn_div = function
y::x::zs -> (x /. y)::zs
| _ -> [nan]
let rpn xs =
let rec iter expr a =
match expr with
[] -> if List.length a = 1 then List.hd a
else nan
| (N x)::xs -> iter xs (x::a)
| Add::xs -> iter xs (rpn_add a)
| Sub::xs -> iter xs (rpn_sub a)
| Mul::xs -> iter xs (rpn_mul a)
| Div::xs -> iter xs (rpn_div a)
in
iter xs []
実際の処理は局所関数 iter で行います。引数 expr が数式を表すリストで、引数 a がスタックを表します。expr が空リストになったら、スタックトップの値を返します。このとき、スタックに複数の値が格納されている場合はエラーのかわりに nan を返します。
次に、先頭要素が数値の場合はそれをスタックに追加します。演算子の場合、対応する関数を呼び出します。このとき、最低でも 2 つの値がスタックになければいけません。y::x::xs とマッチングしない場合はエラーのかわりに [nan] を返します。計算するときは、先頭の要素が第 2 引数、2 番目の要素が第 1 引数になることに注意してください。結果はリスト zs の先頭に追加します。