今回は集合を例題にして、モジュール (ファンクタ) とオブジェクト指向を使ったプログラムを作りましょう。
クラスはモジュール (ファンクタ) の中でも定義することもできます。たとえば、ファンクタ MakeSet の中でクラス set を定義すると、次のようになります。
リスト 9 : ファンクタ内でのクラス定義
(* ストラクチャ *)
module type ITEMTYPE =
sig
type t
val compare : t -> t -> int
end
(* ファンクタ *)
module MakeSet(Item: ITEMTYPE) :
sig
type t = Item.t
class set :
object ('a)
method copy : 'a
method delete : t -> unit
method difference : 'a -> 'a
method insert : t -> unit
method intersection : 'a -> 'a
method is_equal : 'a -> bool
method is_subset : 'a -> bool
method iter : (t -> unit) -> unit
method length : int
method member : t -> bool
method union : 'a -> 'a
end
end
=
struct
type t = Item.t
class set =
object(self : 'self_type)
val mutable content = ([]: t list)
val mutable size = 0
method member p =
let rec mem_eq = function
[] -> false
| x::xs -> if Item.compare p x = 0 then true else mem_eq xs
in
mem_eq content
method insert p =
if not (self#member p) then begin
size <- size + 1;
content <- p::content
end else ()
method delete p =
if self#member p then
(content <- List.filter (fun x -> Item.compare p x <> 0) content;
size <- size - 1)
else raise Not_found
... 省略 ...
end
end
シグネチャでは "class クラス名 : object ... end" でクラス型を定義します。シグネチャでデータ型 t を宣言しているので、t を使ってクラス型を定義します。ファンクタ本体ではデータ型 t を Item.t に定義し、それを使ってクラス set を定義します。要素の比較はストラクチャ Item の関数 compare を使います。あとは今までのプログラムと同じです。
簡単な例として、整数値 (int) を格納する集合 IntSet を作ってみましょう。IntSet を定義すると次のように表示されます。
# module IntSet = MakeSet(struct type t = int let compare x y = x - y end)
module IntSet :
sig
type t = int
class set :
object ('a)
method copy : 'a
method delete : t -> unit
method difference : 'a -> 'a
method insert : t -> unit
method intersection : 'a -> 'a
method is_equal : 'a -> bool
method is_subset : 'a -> bool
method iter : (t -> unit) -> unit
method length : int
method member : t -> bool
method union : 'a -> 'a
end
end
それでは実際に試してみましょう。
# open IntSet;; # let print s = s#iter (fun x -> print_int x#get; print_string " ");; val print : < iter : (int -> unit) -> 'a; .. > -> 'a = <fun> # let a = new set compare;; val a : IntSet.set = <obj> # for i = 1 to 5 do a#insert i done;; - : unit = () # print a;; 5 4 3 2 1 - : unit = () # let b = new set;; val b : IntSet.set = <obj> # for i = 4 to 8 do b#insert i done;; - : unit = () # print b;; 8 7 6 5 4 - : unit = () # print (a#union b);; 1 2 3 8 7 6 5 4 - : unit = () # print (a#intersection b);; 4 5 - : unit = () # print (a#difference b);; 1 2 3 - : unit = ()
このようにファンクタとクラスを組み合わせることも簡単にできます。
ところで、拙作のページ「集合」で作成したクラス set は、要素を比較する関数をクラスの引数に渡しました。ここでは異なる方法を試してみましょう。集合に格納する要素をオブジェクトとし、そのオブジェクトに要素同士を比較するメソッド compare を定義することにします。
それではプログラムを作りましょう。最初にクラスを定義します。
リスト 10 : クラス set の定義
class ['a] set =
object(self: 'self_type)
val mutable content = ([]: 'a list)
val mutable size = 0
method member p =
let rec mem_eq = function
[] -> false
| x::xs -> if p#compare x = 0 then true else mem_eq xs
in
mem_eq content
method insert p =
if not (self#member p) then begin
size <- size + 1;
content <- p::content
end else ()
method delete p =
if self#member p then
(content <- List.filter (fun x -> p#compare x <> 0) content;
size <- size - 1)
else raise Not_found
... 省略 ...
end
今回はオブジェクトのメソッド compare を使ってプログラムを作るので、型推論により型変数 'a はあるオブジェクトの型に制限されます。これはあとで説明します。要素の比較はオブジェクトのメソッド compare を使います。compare の仕様は OCaml の関数 compare と同じです。プログラムは compare p x を p#compare x と書き換えるだけです。
実際に set を定義すると次のように表示されます。
class ['a] set :
object ('b)
constraint 'a = < compare : 'a -> int; .. >
val mutable content : 'a list
val mutable size : int
method copy : 'b
method delete : 'a -> unit
method difference : 'b -> 'b
method insert : 'a -> unit
method intersection : 'b -> 'b
method is_equal : 'b -> bool
method is_subset : 'b -> bool
method iter : ('a -> unit) -> unit
method length : int
method member : 'a -> bool
method union : 'b -> 'b
end
constraint は「制約」という意味で、集合の要素 'a はメソッド compare を持つオブジェクトでなければならないことを表しています。今回は OCaml の型推論にお任せしましたが、プログラムで constraint を記述することもできます。
それでは簡単な実行例を示しましょう。まず最初に、集合に格納するオブジェクトを定義します。
リスト 11 : 要素となるオブジェクト
class ['a] item (x: 'a) =
object(self: 'self_type)
val n = x
method get = n
method compare (x: 'self_type) = compare n x#get
end
データの比較は関数 compare で行います。オブジェクト以外のデータ型であれば、これで大小関係を比較することができます。
実行例は次のようになります。
# let print s = s#iter (fun x -> print_int x#get; print_string " ");; val print : < iter : (< get : int; .. > -> unit) -> 'a; .. > -> 'a = <fun> # let a = new set;; val a : (< compare : 'a -> int; _.. > as 'a) set = <obj> # for i = 1 to 5 do a#insert (new item i) done;; - : unit = () # print a;; 5 4 3 2 1 - : unit = () # let b = new set;; val b : (< compare : 'a -> int; _.. > as 'a) set = <obj> # for i = 4 to 8 do b#insert (new item i) done;; - : unit = () # print b;; 8 7 6 5 4 - : unit = () # print (a#union b);; 1 2 3 8 7 6 5 4 - : unit = () # print (a#intersection b);; 4 5 - : unit = () # print (a#difference b);; 1 2 3 - : unit = ()
最初に集合の要素を表示する関数 print を定義します。型推論により、引数 s はメソッド iter を持つオブジェクトで、iter に渡す関数の引数はメソッド get を持つオブジェクトであることが示されています。
次に、集合 a と b を生成します。a は {1, 2, 3, 4. 5} で、b は {4, 5, 6, 7, 8} です。集合演算を行うと、a と b の和は {1, 2, 3, 4, 5, 6, 7, 8} になり、積は {4, 5} になり、差は {1, 2, 3} になります。
このように、格納するオブジェクトのメソッド compare を使って集合を表すクラスを定義することもできます。
ところで、ファンクタで定義した集合でも、オブジェクトを格納することができます。次の例を見てください。
# module IntObjSet = MakeSet(struct type t = int item
let compare x y = x#compare y end);;
module IntObjSet :
sig
type set
val create : unit -> set
val member : int item -> set -> bool
val insert : int item -> set -> set
val delete : int item -> set -> set
val union : set -> set -> set
val intersection : set -> set -> set
val difference : set -> set -> set
val is_subset : set -> set -> bool
val is_equal : set -> set -> bool
val iter : (int item -> unit) -> set -> unit
val set_of_list : int item list -> set
val list_of_set : set -> int item list
end
# open IntObjSet;;
# let print s = iter (fun x -> print_int x#get; print_string " ") s;;
val print : IntObjSet.set -> unit = <fun>
# let a = set_of_list (List.map (fun x -> new item x) [1;2;3;4;5]);;
val a = IntObjSet.set = <abstr>
# print a;;
1 2 3 4 5 - : unit = ()
# let b = set_of_list (List.map (fun x -> new item x) [4;5;6;7;8]);;
val b = IntObjSet.set = <abstr>
# print b;;
4 5 6 7 8 - : unit = ()
# print (union a b);;
1 2 3 4 5 6 7 8 - : unit = ()
# print (intersection a b);;
4 5 - : unit = ()
# print (difference a b);;
1 2 3 - : unit = ()
ファンクタに渡すストラクチャで、type t = int item とし、compare x y = x#compare x とすれば、オブジェクト item を格納するモジュール IntObjSet を生成することができます。このように、OCaml にはモジュール (ファンクタ) という優れた機能があるので、複数の要素を格納するデータ構造 (コレクション) をクラスで実装することは少ないのかもしれませんね。
可変長配列を操作するモジュール Arraylist をクラスを使わないで定義してください。
リスト : モジュール Arraylist
module Arraylist :
sig
type 'a arraylist
val create : int -> 'a -> 'a arraylist
val push : 'a arraylist -> 'a -> unit
val pop : 'a arraylist -> 'a
val peek : 'a arraylist -> 'a
val get : 'a arraylist -> int -> 'a
val set : 'a arraylist -> int -> 'a -> unit
val length : 'a arraylist -> int
val find_if : ('a -> bool) -> 'a arraylist -> 'a option
val position_if : ('a -> bool) -> 'a arraylist -> int
val count_if : ('a -> bool) -> 'a arraylist -> int
val map : ('a -> 'b) -> 'a arraylist -> 'b arraylist
val filter : ('a -> bool) -> 'a arraylist -> 'a arraylist
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b arraylist -> 'a
val iter : ('a -> 'b) -> 'a arraylist -> unit
end = struct
type 'a arraylist = {mutable buff : 'a array; mutable top : int}
let create init_size init_value =
{buff = Array.make init_size init_value; top = 0}
let push xs x =
if xs.top >= Array.length xs.buff then
let newbuff = Array.make (2 * Array.length xs.buff) xs.buff.(0) in
Array.blit xs.buff 0 newbuff 0 (Array.length xs.buff);
xs.buff <- newbuff
else ();
xs.buff.(xs.top) <- x;
xs.top <- xs.top + 1
let pop xs =
if xs.top = 0 then raise Empty
else (xs.top <- xs.top - 1; xs.buff.(xs.top))
let peek xs =
if xs.top = 0 then raise Empty
else xs.buff.(xs.top - 1)
let get xs i =
if i < 0 || i >= xs.top then raise Out_of_range
else xs.buff.(i)
let set xs i x =
if i < 0 || i >= xs.top then raise Out_of_range
else xs.buff.(i) <- x
let length xs = xs.top
(* 高階関数 *)
let find_if pred xs =
let rec _find i =
if i >= xs.top then None
else if pred xs.buff.(i) then Some xs.buff.(i)
else _find (i + 1)
in _find 0
let position_if pred xs =
let rec _position i =
if i >= xs.top then -1
else if pred xs.buff.(i) then i
else _position (i + 1)
in _position 0
let count_if pred xs =
let rec _count i c =
if i >= xs.top then c
else _count (i + 1) (if pred xs.buff.(i) then c + 1 else c)
in _count 0 0
let map f xs =
let ys = create xs.top (f xs.buff.(0)) in
ys.top <- 1;
for i = 1 to (xs.top - 1) do
push ys (f xs.buff.(i))
done;
ys
let filter pred xs =
let ys = create xs.top xs.buff.(0) in
for i = 0 to (xs.top - 1) do
if pred xs.buff.(i) then push ys xs.buff.(i) else ()
done;
ys
let fold_left f a xs =
let rec _fold i a =
if i >= xs.top then a
else _fold (i + 1) (f a xs.buff.(i))
in _fold 0 a
let iter f xs =
let rec _iter i =
if i >= xs.top then ()
else (f xs.buff.(i); _iter (i + 1))
in _iter 0
end
# open Arraylist;; # let a = create 4 0;; val a : int Arraylist.arraylist = <abstr> # for i = 1 to 8 do push a i done;; - : unit = () # length a;; - : int = 8 # for i = 0 to 7 do print_int (get a i); print_newline() done;; 1 2 3 4 5 6 7 8 - : unit = () # for i = 0 to 7 do set a i ((get a i) * 10) done;; - : unit = () # iter (fun x -> print_int x; print_newline()) a;; 10 20 30 40 50 60 70 80 - : unit = () # iter (fun x -> print_int x; print_newline()) b;; 100 400 900 1600 2500 3600 4900 6400 # let c = filter (fun x -> x mod 20 = 0) a;; val c : int Arraylist.arraylist = <abstr> # iter (fun x -> print_int x; print_newline()) c;; 20 40 60 80 - : unit = () # fold_left (+) 0 a;; - : int = 360 # fold_left (+) 0 b;; - : int = 20400 # find_if (fun x -> x > 50) a;; - : int option = Some 60 # find_if (fun x -> x > 100) a;; - : int option = None # position_if (fun x -> x > 50) a;; - : int = 5 # position_if (fun x -> x > 100) a;; - : int = -1 # count_if (fun x -> x > 50) a;; - : int = 3 # count_if (fun x -> x < 50) a;; - : int = 4 # count_if (fun x -> x < 0) a;; - : int = 0 # for i = 0 to (length a - 1) do print_int (pop a); print_newline() done;; 80 70 60 50 40 30 20 10 - : unit = () # length a;; - : int = 0