「集合 (set)」はいくつかの要素を集めたものです。一般に、集合は重複した要素を含まず、要素の順番に意味はありません。なお、要素の重複を許す集合は「多重集合 (multi set)」と呼ばれます。たとえば、集合 {1, 3, 5, 7} は {7, 5, 3, 1} や {5, 3, 1, 7} と表すこともできます。このように、要素は適当に並べてもかまわないのですが、ある規則で要素を整列させておく場合もあります。
OCaml の場合、標準ライブラリに集合を扱うモジュール Set が用意されていますが、今回は OCaml の勉強ということで、ファンクタを使う方法とオブジェクト指向を使う方法の二通りで set を作ることにします。標準モジュール Set は二分木 (平衡木) を使っていますが、今回は簡単な例題ということでリストを使うことにします。まずは最初にファンクタから作りましょう。
最初にモジュールで定義する関数を表に示します。
| 名前 | 機能 |
|---|---|
| create () | 空の集合を生成する |
| insert x s | 集合 s に要素 x を追加する |
| delete x s | 集合 s から要素 x を削除する |
| member x s | 要素 x は集合 s に含まれているか |
| issubset s1 s2 | s1 は s2 の部分集合か |
| isequal s1 s2 | s1 と s2 は等しいか |
| union s1 s2 | s1 と s2 の和を求める |
| intersection s1 s2 | s1 と s2 の積を求める |
| difference s1 s2 | s1 と s2 の差を求める |
| iter func s | 集合の各要素に関数 func を適用する |
| set_of_list ls | リストを集合に変換する |
| list_of_set s | 集合をリストに変換する |
それではプログラムを作りましょう。最初にファンクタを定義します。
リスト 1 : ファンクタの定義
(* シグネチャの定義 *)
module type ITEMTYPE =
sig
type t
val compare : t -> t -> int
end
(* ファンクタの定義 *)
module MakeSet(Item: ITEMTYPE) :
sig
type set
... 省略 ...
end
=
struct
type set = S of Item.t list
let create () = S []
let rec mem_eq n = function
[] -> false
| x::xs -> if Item.compare n x = 0 then true else mem_eq n xs
let member n (S ls) = mem_eq n ls
let insert n (S ls) =
if mem_eq n ls then S ls else S (n::ls)
let delete n (S ls) =
if mem_eq n ls
then S (List.filter (fun x -> Item.compare n x <> 0) ls)
else raise Not_found
... 省略 ...
end
Item.t は要素の型を表し、type set が集合の型を表します。要素の型 t と要素を比較する関数 compare はシグネチャ ITEMTYPE で規定し、それを定義したモジュールをファンクタ MakeSet に渡します。関数 create は空の集合 S [] を生成して返します。mem_eq はモジュール内で使用する関数で、リストの中から x と等しい要素を探します。
関数 member は mem_eq を呼び出すだけです。関数 insert は mem_eq を呼び出して、n がリスト ls に含まれていなければ、リストの先頭に n を追加した新しい集合を返します。そうでなければ、集合をそのまま返します。関数 delete も簡単です。mem_eq で引数 n を探し、見つからない場合は例外 Not_found を送出します。見つけた場合は List.filter で ls から n を削除した集合を返します。
関数 is_subset と is_equal も簡単です。プログラムは次のようになります。
リスト 2 : 集合の同値と包含関係の判定
(* 部分集合の判定 *)
let is_subset (S ls1) (S ls2) =
let rec iter = function
[] -> true
| x::xs -> if mem_eq x ls2 then iter xs else false
in
iter ls1
(* 同値の判定 *)
let is_equal s1 s2 =
is_subset s1 s2 && is_subset s2 s1
集合 s1 の要素が集合 s2 にすべて含まれている場合、is_subset は true を返します。異なる要素があれば部分集合ではないので false を返します。実際の処理は局所関数 iter で行っています。リスト ls1 の要素を順番に取り出して、リスト ls2 に含まれているか mem_eq でチェックします。含まれていない要素があれば false を返します。すべての要素が ls2 に含まれていれば true を返します。
集合の同値関係は、s1 が s2 の部分集合で、かつ s2 が s1 の部分集合のときに成立します。したがって、is_equal は is_subset s1 s2 && is_subset s2 s1 をチェックするだけです。
次は 2 つの集合の和を求める関数 union を作ります。プログラムは次のようになります。
リスト 3 : 集合の和を求める
let union (S ls1) (S ls2) =
let rec _union = function
[] -> ls2
| x::xs when mem_eq x ls2 -> _union xs
| x::xs -> x :: (_union xs)
in
S (_union ls1)
union は集合 s1 と s2 の和を計算します。実際の処理は局所関数 _union で行います。_union の引数はリスト ls1 です。ls1 の要素 x が ls2 に含まれていなければ、その要素 x を新しいリストに追加します。この処理を再帰呼び出しで行っています。
関数 _union の引数が空リストの場合は、ls2 をそのまま返します。union は集合 s2 の連結リストを共有することに注意してください。次に、ls1 の要素 x が ls に含まれている場合は _union を再帰呼び出しして、その返り値をそのまま返します。そうでない場合は、x を新しいリストに追加します。あとは、_union を呼び出して新しいリストを生成して返すだけです。
次は 2 つの集合の積を求める関数 intersection を作ります。
リスト 4 : 集合の積を求める
let intersection (S ls1) (S ls2) =
let rec _inter = function
[] -> []
| x::xs when mem_eq x ls2 -> x :: (_inter xs)
| _::xs -> _inter xs
in
S (_inter ls1)
関数 intersection は集合 s1 と s2 の積を計算します。実際の処理は局所関数 _inter で行います。_inter の引数は s1 のリスト ls1 です。ls1 の要素 x が ls2 に含まれている場合は、その要素を新しいリストに追加します。この処理を再帰呼び出しで行っています。
関数 _inter の引数が空リストの場合は、空リストを返します。次に、要素 x が ls2 に含まれている場合は x を新しいリストに追加します。そうでなければ、_inter の返り値をそのまま返します。あとは、_inter を呼び出して新しいリストを生成して返すだけです。
次は集合の差を求める関数 difference を作ります。
リスト 5 : 集合の差を求める
let difference (S ls1) (S ls2) =
let rec _diff = function
[] -> []
| x::xs when mem_eq x ls2 -> _diff xs
| x::xs -> x :: (_diff xs)
in
S (_diff ls1)
関数 difference は集合 s1 と s2 の差を計算します。実際の処理は局所関数 _diff で行います。_diff の引数は s1 のリスト ls1 です。ls1 の要素 x が ls2 に含まれていない場合は、その要素を新しいリストに追加します。この処理を再帰呼び出しで行っています。
関数 _diff の引数が空リストの場合は、空リストを返します。次に、要素 x が ls2 に含まれている場合は _diff の返り値をそのまま返します。そうでなければ、x を新しいリストに追加して返します。あとは、_diff を呼び出して新しいリストを生成して返すだけです。
あとはとくに難しいところはないでしょう。詳細はプログラムリスト１をお読みください。また、要素の個数が多くなるとリストでは処理が遅くなってしまいます。その場合は二分木やハッシュ法を使うと良いでしょう。
それでは実際に実行してみましょう。
# module IntSet = MakeSet(struct type t = int let compare x y = x - y end);; ... 省略 ... # open IntSet;; # let print s = iter (fun x -> print_int x; print_string " ") s;; val print : IntSet.set -> unit = <fun> # let a = set_of_list [1; 2; 3; 4; 5];; val a : IntSet.set = <abstr> # print a;; 1 2 3 4 5 - : unit = () # member 1 a;; - : bool = true # member 6 a;; - : bool = false # let b = set_of_list [4; 5; 6; 7; 8];; val b : IntSet.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 = ()
正常に動作していますね。
| 名前 | 機能 |
|---|---|
| s#insert x | 集合 s に要素 x を追加する |
| s#delete x | 集合 s から要素 x を削除する |
| s#member x | 要素 x は集合 s に含まれているか |
| s#length | 集合 s に含まれている要素の個数を返す |
| s#copy | 集合 s をコピーした新しい集合を返す |
| s1#is_subset s2 | s1 は s2 の部分集合か |
| s1#is_equal s2 | s1 と s2 は等しいか |
| s1#union s2 | s1 と s2 の和を求める |
| s1#intersection s2 | s1 と s2 の積を求める |
| s1#difference s2 | s1 と s2 の差を求める |
| s#iter func | 集合 s の各要素に関数 func を適用する |
次はオブジェクト指向で集合 set を作りましょう。ファンクタでは要素を比較する関数をストラクチャに定義して渡しました。クラス set の場合も、要素を比較する関数をクラスの引数に渡すことにしましょう。なお、集合に格納する要素をオブジェクトとし、そのオブジェクトに要素同士を比較するメソッドを定義する方法もあります。定義するメソッドを表 2 に示します。
それではプログラムを作りましょう。最初にクラスを定義します。
リスト 6 : クラス set の定義
class ['a] set compare =
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 compare p x = 0 then true else mem_eq xs
in
mem_eq content
... 省略 ...
end
クラス名は set としました。要素のデータ型は型変数 'a で表しています。引数 compare は要素を比較する関数で、データ型は 'a -> 'a -> int です。インスタンス変数 content に要素を格納するリストをセットします。インスタンス変数 size は格納している要素の個数を表します。
メソッド member は content のリストの中から引数 p と等しい要素を探します。実際の処理は局所関数 mem_eq で行います。要素の比較は引数に渡された関数 compare を使います。compare の仕様は OCaml の関数 compare と同じです。mem_eq は等しい要素を見つけたら true を返し、見つからない場合は false を返します。
メソッド insert と delete は member を使うと簡単です。次のリストを見てください。
リスト 7 : データの挿入と削除
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 -> compare p x <> 0) content;
size <- size - 1)
else raise Not_found
最初に引数 p が集合に含まれているか self#member でチェックします。含まれていない場合、insert は content の先頭に p を追加し、delete は例外 Not_Found を送出します。p が集合に含まれている場合、insert は何もしません。delete は List.filter で content から p を削除します。
次はメソッド is_subset と is_equal を作ります。
リスト 8 : 集合の同値と包含関係の判定
(* 部分集合の判定 *)
method is_subset (other: 'self_type) =
let rec iter = function
[] -> true
| x::xs -> if other#member x then iter xs else false
in
iter content
(* 同値の判定 *)
method is_equal (other: 'self_type) =
self#length = other#length && self#is_subset other
is_subset や is_equal, union など集合演算を行うメソッドは、呼び出し元のオブジェクトと同じデータ型のオブジェクトを引数に受け取ります。このようなメソッドを「バイナリメソッド (binary method)」といいます。この場合、呼び出し元のオブジェクトと同じデータ型であることを表すため、引数にデータ型を指定する必要があります。
ここで、引数 other のデータ型を 'a set とすると、クラスを「継承」するときに問題が発生します。この問題については継承のところで説明します。このため、OCaml は呼び出し元のオブジェクトの型を次の形式で指定できるようになっています。
object (変数名: 型式) ... end
object (self: 'self_type) で self のデータ型を型変数 'self_type で表しています。バイナリメソッドの場合、引数のデータ型は 'self_type で指定します。
is_subset と is_equal の処理内容は簡単です。is_subset は content の要素が other に含まれているかチェックし、含まれていない要素があれば false を返します。is_equal は self と other の要素数が等しくて、is_subset が真であれば true を返します。
次は集合演算を行うメソッドを作ります。
リスト 9 : 集合演算を行うメソッド
(* 集合のコピー *)
method copy = {< >}
(* 集合の和 *)
method union (other: 'self_type) =
let a = other#copy in
List.iter (fun x -> a#insert x) content;
a
(* 集合の積 *)
method intersection (other: 'self_type) =
let a = {< content = []; size = 0 >} in
List.iter (fun x -> if other#member x then a#insert x) content;
a
(* 集合の差 *)
method difference (other: 'self_type) =
let a = {< content = []; size = 0 >} in
List.iter (fun x -> if not (other#member x) then a#insert x) content;
a
新しい集合を生成するとき、new set で行うとバイナリメソッドと同様に継承で問題が発生します。そこで、OCaml に用意されているオブジェクトをコピーする機能を使うことにします。
{< インスタンス変数1 = 式1; インスタンス変数2 = 式2; ... >}
メソッド内で {< ... >} を使うと呼び出し元と同じ型のオブジェクトを生成し、インスタンス変数の値をコピーします。このとき、インスタンス変数の値を書き換えることができます。{< >} とすると、値の書き換えは行われません。
また、コピーはインスタンス変数の値をそのまま新しいインスタンス変数にセットするだけです。たとえば、インスタンス変数の値がリストや参照型データの場合、リストや参照先のデータがコピーされることはありません。これを「浅いコピー」といいます。
メソッド copy はオブジェクトをコピーして返します。オブジェクトを s とすると、s#copy で s をコピーすることができます。なお、この動作は OCaml のモジュール Oo に用意されている関数 copy と同じです。Oo.copy obj はオブジェクト obj をコピーして返します。ただし、インスタンス変数の値を書き換えることはできません。
集合演算 union, intersection, difference はオブジェクトをコピーして、そこに条件を満たす要素をメソッド insert で挿入していくだけです。最後にコピーしたオブジェクトを返します。
あとは特に難しいところはないでしょう。詳細はプログラムリスト２をお読みください。
実際に set を定義すると次のように表示されます。
class ['a] set :
('a -> 'a -> int) ->
object ('b)
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
それでは簡単な実行例を示しましょう。
# 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 : '_a 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 compare;; val b : '_a 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 = ()
最初に集合の要素を表示する関数 print を定義します。型推論により、引数 s はメソッド iter を持つオブジェクトで、iter に渡す関数の引数は int であることが示されています。
次に、集合 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} になります。これらのメソッドは正常に動作していますね。このように、オブジェクト指向でも簡単に集合 set を作ることができます。
(*
* 集合 : ファンクタ版
*
* Copyright (C) 2008-2020 Makoto Hiroi
*)
(* シグネチャの定義 *)
module type ITEMTYPE =
sig
type t
val compare : t -> t -> int
end
(* ファンクタの定義 *)
module MakeSet(Item: ITEMTYPE) :
sig
type set
val create : unit -> set
val member : Item.t -> set -> bool
val insert : Item.t -> set -> set
val delete : Item.t -> 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 : (Item.t -> unit) -> set -> unit
val set_of_list : Item.t list -> set
val list_of_set : set -> Item.t list
end
=
struct
type set = S of Item.t list
let create () = S []
let rec mem_eq n = function
[] -> false
| x::xs -> if Item.compare n x = 0 then true else mem_eq n xs
let member n (S ls) = mem_eq n ls
let insert n (S ls) =
if mem_eq n ls then S ls else S (n::ls)
let delete n (S ls) =
if mem_eq n ls
then S (List.filter (fun x -> Item.compare n x <> 0) ls)
else raise Not_found
let is_subset (S ls1) (S ls2) =
let rec iter = function
[] -> true
| x::xs -> if mem_eq x ls2 then iter xs else false
in
iter ls1
let is_equal s1 s2 =
is_subset s1 s2 && is_subset s2 s1
(* 集合演算 *)
let union (S ls1) (S ls2) =
let rec _union = function
[] -> ls2
| x::xs when mem_eq x ls2 -> _union xs
| x::xs -> x :: (_union xs)
in
S (_union ls1)
let intersection (S ls1) (S ls2) =
let rec _inter = function
[] -> []
| x::xs when mem_eq x ls2 -> x :: (_inter xs)
| _::xs -> _inter xs
in
S (_inter ls1)
let difference (S ls1) (S ls2) =
let rec _diff = function
[] -> []
| x::xs when mem_eq x ls2 -> _diff xs
| x::xs -> x :: (_diff xs)
in
S (_diff ls1)
let iter f (S ls) = List.iter (fun x -> f x) ls
let set_of_list ls =
List.fold_right (fun x y -> insert x y) ls (S [])
let list_of_set (S ls) = ls
end
(*
* 集合 : オブジェクト指向版
*
* Copyright (C) 2008-2020 Makoto Hiroi
*)
(* 集合 *)
class ['a] set compare =
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 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 -> compare p x <> 0) content;
size <- size - 1)
else raise Not_found
method length = size
method iter f = List.iter f content
(* 集合演算 *)
method copy = {< >}
method union (other: 'self_type) =
let a = other#copy in
List.iter (fun x -> a#insert x) content;
a
method intersection (other: 'self_type) =
let a = {< content = []; size = 0 >} in
List.iter (fun x -> if other#member x then a#insert x) content;
a
method difference (other: 'self_type) =
let a = {< content = []; size = 0 >} in
List.iter (fun x -> if not (other#member x) then a#insert x) content;
a
method is_subset (other: 'self_type) =
let rec iter = function
[] -> true
| x::xs -> if other#member x then iter xs else false
in
iter content
method is_equal (other: 'self_type) =
self#length = other#length && self#is_subset other
end
n 次元のベクトルを表すクラス vector とその操作メソッドを定義してください。ベクトルは float list で表すものとします。
リスト : ベクトル (vector)
(* 例外 *)
exception Dim_error
class vector (init: float list) =
object(self: 'self_type)
val xs = init
val size = List.length init
method content = xs
method length = size
(* 要素同士の演算 *)
method add (other: 'self_type) =
if other#length <> size then raise Dim_error
else new vector (List.map2 (+.) xs other#content)
method sub (other: 'self_type) =
if other#length <> size then raise Dim_error
else new vector (List.map2 (-.) xs other#content)
method mul (other: 'self_type) =
if other#length <> size then raise Dim_error
else new vector (List.map2 ( *. ) xs other#content)
method div (other: 'self_type) =
if other#length <> size then raise Dim_error
else new vector (List.map2 (/.) xs other#content)
(* スカラー演算 *)
method add_scalar k =
new vector (List.map ((+.) k) xs)
method mul_scalar k =
new vector (List.map (( *. ) k) xs)
(* 内積 *)
method dot (other: 'self_type) =
if other#length <> size then raise Dim_error
else List.fold_left2 (fun a x y -> x *. y +. a) 0.0 xs other#content
(* 大きさ *)
method norm =
sqrt (List.fold_left (fun a x -> x *. x +. a) 0.0 xs)
end
exception Dim_error
class vector :
float list ->
object ('a)
val size : int
val xs : float list
method add : 'a -> vector
method add_scalar : float -> vector
method content : float list
method div : 'a -> vector
method dot : 'a -> float
method length : int
method mul : 'a -> vector
method mul_scalar : float -> vector
method norm : float
method sub : 'a -> vector
end
new でベクトルを生成するとき、引数に float list を渡します。ベクトルの次元数が合わない場合、例外 Dim_error を送出することにします。ベクトルの要素同士の演算は List.map2 を使うと簡単です。map2 の使用例を示します。
# List.map2;;
- : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list = <fun>
# List.map2 (+) [1; 2; 3] [4; 5; 6];;
- : int list = [5; 7; 9]
# List.map2 ( * ) [1; 2; 3] [4; 5; 6];;
- : int list = [4; 10; 18]
スカラーとの演算は List.map を使えばいいですね。ベクトルの大きさは List.fold_left を、内積は List.fold_left2 を使うと簡単です。fold_left2 の使用例を示します。
# List.fold_left2;;
- : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a = <fun>
# List.fold_left2;;
- : ('a -> 'b -> 'c -> 'a) -> 'a -> 'b list -> 'c list -> 'a = <fun>
# List.fold_left2 (fun a b c -> (b, c)::a) [] [1; 2; 3] [4; 5; 6];;
- : (int * int) list = [(3, 6); (2, 5); (1, 4)]
# List.fold_left2 (fun a b c -> b * c + a) 0 [1; 2; 3] [4; 5; 6];;
- : int = 32
それでは実際に試してみましょう。
# let a = new vector [1.; 1.; 1.];; val a : vector = <obj> # let b = new vector [1.; 2.; 3.];; val b : vector = <obj> # let zero = new vector [0.; 0.; 0.];; val zero : vector = <obj> # (a#add zero)#content;; - : float list = [1.; 1.; 1.] # (zero#add b)#content;; - : float list = [1.; 2.; 3.] # (a#add b)#content;; - : float list = [2.; 3.; 4.] # (a#sub zero)#content;; - : float list = [1.; 1.; 1.] # (zero#sub a)#content;; - : float list = [-1.; -1.; -1.] # (a#sub b)#content;; - : float list = [0.; -1.; -2.] # (a#sub a)#content;; - : float list = [0.; 0.; 0.] # (a#mul zero)#content;; - : float list = [0.; 0.; 0.] # (zero#mul a)#content;; - : float list = [0.; 0.; 0.] # (a#mul b)#content;; - : float list = [1.; 2.; 3.] # (a#mul a)#content;; - : float list = [1.; 1.; 1.] # (b#mul b)#content;; - : float list = [1.; 4.; 9.] # (zero#div a)#content;; - : float list = [0.; 0.; 0.] # (b#div a)#content;; - : float list = [1.; 2.; 3.] # (a#div b)#content;; - : float list = [1.; 0.5; 0.333333333333333315] # (b#div b)#content;; - : float list = [1.; 1.; 1.] # (zero#add_scalar 10.)#content;; - : float list = [10.; 10.; 10.] # (a#mul_scalar 100.)#content;; - : float list = [100.; 100.; 100.] # a#norm;; - : float = 1.73205080756887719 # b#norm;; - : float = 3.74165738677394133 # a#dot b;; - : float = 6. # a#dot zero;; - : float = 0. # b#dot b;; - : float = 14.
正常に動作しているようです。興味のある方はいろいろ試してみてください。