5.2 クラスを用いた簡単なモジュール

5.2.1. 文字列
5.2.2. スタック
5.2.3. ハッシュテーブル
5.2.4. 集合

整数や文字列のようなプリミティブ型をオブジェクトとして扱うことができるのかどうか疑問に思った人もいるでしょう。数や文字列といった例は一般におもしろいものではないものの、それが要求されるような状況もあります。上の money クラスはその一例です。ここでは文字列を対象にする方法を示します。

5.2.1 文字列

文字列をオブジェクトとしてナイーブに定義すると次のようになるでしょう。

#class ostring s =
   object
      method get n = String.get s n
      method set n c = String.set s n c
      method print = print_string s
      method copy = new ostring (String.copy s)
   end;;
class ostring :
  string ->
  object
    method copy : ostring
    method get : int -> char
    method print : unit
    method set : int -> char -> unit
  end
      

この copy メソッドは現在のクラスのオブジェクトではなく ostring クラスのオブジェクトを返します。したがって、これ以降にクラスを拡張した場合、 copy メソッドは親クラスのオブジェクトを返すことになってしまいます。

#class sub_string s =
   object
      inherit ostring s
      method sub start len = new sub_string (String.sub s  start len)
   end;;
class sub_string :
  string ->
  object
    method copy : ostring
    method get : int -> char
    method print : unit
    method set : int -> char -> unit
    method sub : int -> int -> sub_string
  end
      

3.13 節「関数型オブジェクト」 で見た通り、解決策は {< >} を使うことです。文字列の表現 s を格納するためのインスタンス変数が必要になります。

#class better_string s =
   object
      val repr = s
      method get n = String.get repr n
      method set n c = String.set repr n c
      method print = print_string repr
      method copy = {< repr = String.copy repr >}
      method sub start len = {< repr = String.sub s  start len >}
   end;;
class better_string :
  string ->
  object ('a)
    val repr : string
    method copy : 'a
    method get : int -> char
    method print : unit
    method set : int -> char -> unit
    method sub : int -> int -> 'a
  end
      

推論された型で示されているように、メソッド copysub は クラスの型と同じ型をもつオブジェクトを返すようになります。

他の難しい点は concat メソッドの実装です。ある文字列を同一のクラスの他の文字列と連結するには、インスタンス変数に外部からアクセスできなければなりません。そのためには s を返すメソッド repr を定義しなければなりません。ここに、文字列の正しい定義を示します。

#class ostring s =
   object (self : 'mytype)
      val repr = s
      method repr = repr
      method get n = String.get repr n
      method set n c = String.set repr n c
      method print = print_string repr
      method copy = {< repr = String.copy repr >}
      method sub start len = {< repr = String.sub s start len >}
      method concat (t : 'mytype) = {< repr = repr ^ t repr >}
   end;;
class ostring :
  string ->
  object ('a)
    val repr : string
    method concat : 'a -> 'a
    method copy : 'a
    method get : int -> char
    method print : unit
    method repr : string
    method set : int -> char -> unit
    method sub : int -> int -> 'a
  end
      

別の構築子として、与えられた長さの未初期化の文字列を返すものも定義できます。

#class cstring n = ostring (String.create n);;
class cstring : int -> ostring
      

ここでは文字列の表現を公開してもおそらく害はありません。 3.17 節「Friend」money で通貨を隠蔽したとの同様に文字列の表現を隠すこともできます。

5.2.2 スタック

データ型をパラメータとしたいときにモジュールを使うべきかクラスを使うべきかの選択を迫られることもあります。実際にどちらの方法でもまったく同じようなものになることもあります。例えば、スタックはクラスとして素直に実装することができます。

#exception Empty;;
exception Empty

#class ['a] stack =
   object 
     val mutable l = ([] : 'a list)
     method push x = l <- x::l
     method pop = match l with [] -> raise Empty | a::l' -> l <- l'; a
     method clear = l <- []
     method length = List.length l
   end;;
class ['a] stack :
  object
    val mutable l : 'a list
    method clear : unit
    method length : int
    method pop : 'a
    method push : 'a -> unit
  end
      

ですが、スタックの要素に対して繰り返すメソッドを書くときに問題が起こります。 fold メソッドの型は ('b -> 'a -> 'b) -> 'b -> 'b になるでしょう。ここで、 'a はスタックのパラメータです。パラメータ 'b はクラス 'a stack ではなく fold メソッドに渡された引数に関係しています。ナイーブな方法は、 'bstack クラスのパラメータに追加することでしょう。

#class ['a, 'b] stack2 =
   object
     inherit ['a] stack
     method fold f (x : 'b) = List.fold_left f x l
   end;;
class ['a, 'b] stack2 :
  object
    val mutable l : 'a list
    method clear : unit
    method fold : ('b -> 'a -> 'b) -> 'b -> 'b
    method length : int
    method pop : 'a
    method push : 'a -> unit
  end
      

しかし、あるオブジェクトのメソッド fold は同じ型を持つ関数群にしか適用できません。

#let s = new stack2;;
val s : ('_a, '_b) stack2 = <obj>

#s#fold (+) 0;;
- : int = 0

#s;;
- : (int, int) stack2 = <obj>
      

より良い解は多相メソッドを使うことです。多相メソッドは Objective Caml バージョン 3.05 で導入されました。 多相メソッドを使うと fold の型の 型変数 'b を全称修飾することができるようになり、 fold の型は多相型 Forall 'b. ('b -> 'a -> 'b) -> 'b -> 'b になります。型検査器は、独力では多相型を推論できないため、メソッド fold には陽な型宣言が必要になります。

#class ['a] stack3 =
   object
     inherit ['a] stack
     method fold : 'b. ('b -> 'a -> 'b) -> 'b -> 'b
                 = fun f x -> List.fold_left f x l
   end;;
class ['a] stack3 :
  object
    val mutable l : 'a list
    method clear : unit
    method fold : ('b -> 'a -> 'b) -> 'b -> 'b
    method length : int
    method pop : 'a
    method push : 'a -> unit
  end
      

5.2.3 ハッシュテーブル

オブジェクト指向ハッシュテーブルの簡略版は次のようなクラス型になります。

#class type ['a, 'b] hash_table =
   object 
     method find : 'a -> 'b
     method add : 'a -> 'b -> unit
   end;;
class type ['a, 'b] hash_table =
  object method add : 'a -> 'b -> unit method find : 'a -> 'b end
      

簡略版の実装には連想リストを使います。連想リストは小さなハッシュテーブルの実装に非常に適しています。

#class ['a, 'b] small_hashtbl : ['a, 'b] hash_table =
   object
     val mutable table = []
     method find key = List.assoc key table
     method add key valeur = table <- (key, valeur) :: table
   end;;
class ['a, 'b] small_hashtbl : ['a, 'b] hash_table
      

うまくスケールするよりよい実装は小さなハッシュテーブルを要素とする真のハッシュテーブルを使うことです。

#class ['a, 'b] hashtbl size : ['a, 'b] hash_table =
   object (self)
     val table = Array.init size (fun i -> new small_hashtbl) 
     method private hash key =
       (Hashtbl.hash key) mod (Array.length table)
     method find key = table.(self hash key)   find key
     method add key = table.(self hash key)   add key
   end;;
class ['a, 'b] hashtbl : int -> ['a, 'b] hash_table
      

5.2.4 集合

集合の実装には別の難しさがあります。 union メソッドは同一のクラスの別のオブジェクトの内部表現にアクセスできる必要があります。

これは 3.17 節「Friend」 で見たフレンド関数の別例です。実際、 Set モジュールではこれと同じ仕組みをオブジェクトなしで使っています。

オブジェクト指向版の集合では、集合の表現を返すメソッド tag を追加する必要があります。集合は要素の型をパラメータとするので、 tag メソッドは多相型 'a tag となり、モジュール定義においては具象型ですが、シグネチャにおいては抽象型です。外部では同一の型の tag メソッドを持つオブジェクトは同一の表現を共有することが保証されます。

#module type SET =
   sig
     type 'a tag
     class ['a] c :
       object ('b)
         method is_empty : bool
         method mem : 'a -> bool
         method add : 'a -> 'b
         method union : 'b -> 'b
         method iter : ('a -> unit) -> unit
         method tag : 'a tag
       end
   end;;

#module Set : SET =
   struct
     let rec merge l1 l2 =
       match l1 with
         [] -> l2
       | h1 :: t1 ->
           match l2 with
             [] -> l1
           | h2 :: t2 ->
               if h1 < h2 then h1 :: merge t1 l2
               else if h1 > h2 then h2 :: merge l1 t2
               else merge t1 l2
     type 'a tag = 'a list
     class ['a] c =
       object (_ : 'b)
         val repr = ([] : 'a list)
         method is_empty = (repr = [])
         method mem x = List.exists ((=) x) repr
         method add x = {< repr = merge [x] repr >}
         method union (s : 'b) = {< repr = merge repr s tag >}
         method iter (f : 'a -> unit) = List.iter f repr
         method tag = repr
       end
   end;;