1.4 レコードとバリアント

ユーザ定義データ構造にはレコードとバリアントがあり、ともに type 宣言で定義できます。ここでは有理数を表すレコード型を宣言してみます。

#type ratio = {num: int; denum: int};;
type ratio = { num : int; denum : int; } 

#let add_ratio r1 r2 =
   {num = r1.num * r2.denum + r2.num * r1.denum;
    denum = r1.denum * r2.denum};;
val add_ratio : ratio -> ratio -> ratio = <fun>

#add_ratio {num=1; denum=3} {num=2; denum=5};;
- : ratio = {num = 11; denum = 15}
    

バリアント型の宣言には、その型の値が取りうる形を全て並べます。 それぞれのケースは構成子と呼ばれる名前で識別されます。構成子は、そのバリアント型の値を構成するためと、パターンマッチングのために使われます。構成子の名前は変数名と区別するため大文字で書きます(変数名は小文字で始まります)。以下に(整数と浮動小数点数の)数値を混ぜて計算するためのバリアント型を示します。

#type number = Int of int | Float of float | Error;;
type number = Int of int | Float of float | Error
    

この宣言は number 型が、整数か浮動小数点数か(0 除算などの)不正な演算を表す定数 Error の 3 つしか取りえないことを意味します。

列挙型はバリアントの特殊な場合で、すべての選択肢が定数の場合です。

#type sign = Positive | Negative;;
type sign = Positive | Negative

#let sign_int n = if n >= 0 then Positive else Negative;;
val sign_int : int -> sign = <fun>
    

number 型の算術演算を定義するには、2 つの number 型値に対してパターンマッチングを用います。

#let add_num n1 n2 =
   match (n1, n2) with
      (Int i1, Int i2) ->
       (* Check for overflow of integer addition *)
       if sign_int i1 = sign_int i2 && sign_int(i1 + i2) <> sign_int i1
       then Float(float i1 +. float i2)
       else Int(i1 + i2)
   | (Int i1, Float f2) -> Float(float i1 +. f2)
   | (Float f1, Int i2) -> Float(f1 +. float i2)
   | (Float f1, Float f2) -> Float(f1 +. f2)
   | (Error, _) -> Error
   | (_, Error) -> Error;;
val add_num : number -> number -> number = <fun>

#add_num (Int 123) (Float 3.14159);;
- : number = Float 126.14159
    

バリアント型の主な用途は再帰的なデータ構造の記述です。例として二分木を考えてみましょう。

#type 'a btree = Empty | Node of 'a * 'a btree * 'a btree;;
type 'a btree = Empty | Node of 'a * 'a btree * 'a btree
    

これは、'a 型(任意の型)の値を持つ二分木は、空(Empty)か、 'a 型の値と 2 つの部分木を持つ節(Node)で構成されるという意味です。部分木もまた 'a 型の値を格納する 'a btree 型なります。

二分木の処理は、データ構造の型定義に従うような再帰関数で自然に表現出来ます。例として、ソートされた二分木に探索と挿入を行う関数を示します(右の部分木の要素が左の部分木の要素より大きいものとします)

#let rec member x btree =
   match btree with
     Empty -> false
   | Node(y, left, right) ->
       if x = y then true else
       if x < y then member x left else member x right;;
val member : 'a -> 'a btree -> bool = <fun>

#let rec insert x btree =
   match btree with
     Empty -> Node(x, Empty, Empty)
   | Node(y, left, right) ->
       if x <= y then Node(y, insert x left, right)
                 else Node(y, left, insert x right);;
val insert : 'a -> 'a btree -> 'a btree = <fun>