Functional Programming

多重継承と Mix-in

前回は単一継承について簡単に説明し、具体的な例題としてスタック stack を継承して格納する要素の個数を制限するスタック fixed_stack と、集合 set を継承して要素を昇順に並べて格納する sorted_set を作成しました。今回は多重継承と Mix-in について説明します。

●多重継承の使い方

最初に、多重継承について簡単に説明します。例題として、foo と bar の 2 つのクラスを継承するクラス baz を考えてみましょう。まず、foo と bar を定義します (リスト 1, 2)。

リスト 1 : クラス foo の定義

class foo (x: int) =
  object
    val mutable a = x
    method get_a = a
    method set_a x = a <- x
    method print = Printf.printf "foo#method %d" a
  end

リスト 2 : クラス bar の定義

class bar (x: int) =
  object
    val mutable b = x
    method get_b = b
    method set_b x = b <- x
    method print = Printf.printf "bar#method %d" b
  end

クラス foo にはインスタンス変数 a とメソッド get_a, set_a、クラス bar にはインスタンス変数 b とメソッド get_b, set_b が定義されています。そして、両方のクラスともメソッド print が定義されています。foo と bar を継承するクラス Baz はリスト 3 のように定義されます。

リスト 3 : クラス baz の定義

class baz x y =
  object
    inherit foo x
    inherit bar y
  end

inherit で foo と bar を指定します。これで foo と bar を多重継承することができます。実際にクラスを定義すると次のように表示されます。

class foo :
  int ->
  object
    val mutable a : int
    method get_a : int
    method print : unit
    method set_a : int -> unit
  end

class bar :
  int ->
  object
    val mutable b : int
    method get_b : int
    method print : unit
    method set_b : int -> unit
  end

class baz :
  int ->
  int ->
  object
    val mutable a : int
    val mutable b : int
    method get_a : int
    method get_b : int
    method print : unit
    method set_a : int -> unit
    method set_b : int -> unit
  end

それでは実際に試してみましょう。

# let a = new baz 1 2;;
val a : baz = <obj>
# a#get_a;;
- : 1
# a#get_b;;
- : 2
# a#print;;
bar#method 2 - : unit = ()

継承したメソッド get_a と get_b を呼び出すことができるのは当然ですが、両方のクラスにある print は、どちらのクラスのメソッドが呼び出されるのでしょうか。表示された bar#method から、クラス bar のメソッドが呼び出されたことがわかります。

多重継承したクラスで同名のメソッドが存在する場合、OCaml では最後に inherit されたクラスのメソッドが有効になります。この例では、最初に foo を inherit して、次に bar を inherit しています。したがって、メソッド print はクラス bar のメソッドが有効になります。もしも、bar を inherit してから foo を inherit すると、今度は foo のメソッド print が有効になります。

このように、inherit する順番で継承されるメソッドが変化することに注意してください。なお、inherit でスーパークラスの参照名を定義すれば、そのクラスのメソッドを呼び出すことは可能です。次の例を見てください。

リスト 4 : 多重継承のメソッド結合

class baz1 x y = object
  inherit foo x as super1
  inherit bar y as super2
  method print = super1#print; print_newline(); super2#print
end

クラス baz1 ではメソッド print をオーバーライドして、foo と bar のメソッド print を呼び出しています。それでは実際に試してみましょう。

# let c = new baz1 1 2;;
val c : baz1 = <obj>
# c#print;;
foo#method 1
bar#method 2 - : unit = ()

このように、スーパークラス foo と baz のメソッド print を呼び出すことができます。

●多重継承の問題点

多重継承を使う場合、異なる性質や機能を持つクラスを継承することがあります。たとえば、クラス foo にはメソッド method_a があり、クラス bar にはメソッド method_b があるとしましょう。この 2 つのメソッドはまったく異なる働きをします。ここで、メソッド method_a はインスタンス変数 x を使っていて、method_b も変数 x を使っていると、多重継承で問題が発生します。

クラス foo と bar を多重継承してクラス baz を作成した場合、クラス baz のインスタンスには変数 x がひとつ ^[*1] しかありません。メソッド method_a と method_b はひとつしかない変数 x を使うことになります。この場合、どちらかのメソッドは正常に動作しないでしょう。これでは多重継承する意味がありません。これが多重継承の問題点です。

このように、多重継承はどんなクラスでもできるというわけではありません。同名のインスタンス変数を持つクラスは多重継承できないと考えた方がよいでしょう。それから、多重継承にはもうひとつ問題点があります。それはクラスの階層構造が複雑になることです。

単一継承の場合、クラスの階層は木構造になりますが、多重継承ではグラフになります。木構造の場合、クラスの優先順位は簡単にわかりますが、グラフになると優先順位を理解するのは難しくなります。多重継承は強力な機能ですが、使うときには十分な注意が必要なのです。

●Mix-in

これらの問題を回避するため、インスタンス変数 (属性) を継承するスーパークラスはひとつだけに限定して、あとのスーパークラスはメソッド (実装) だけを継承するという方法があります。この方法を Mix-in といいます。

具体的には、インスタンス変数を定義せずにメソッドだけを記述したクラスを用意します。属性の継承は単一継承になりますが、実装のみを記述したクラスはいくつ継承してかまいません。ひとつのクラスに複数の実装を混ぜることから Mix-in と呼ばれています。

なお、Mix-in は特別な機能ではなく、多重継承を使いこなすための方法論にすぎません。多重継承を扱うことができるプログラミング言語であれば Mix-in を行うことが可能です。ちなみに、この Mix-in という方法を言語仕様に取り込んだのが Ruby です。

OCaml は多重継承をサポートしているので、Mix-in を利用することができます。図 1 を見てください。

        図 1 : Mix-in

クラス C はクラス B を継承していて、そこにクラス Mixin A が Mix-in されています。クラス D もクラス B を継承していますが、Mix-in されているクラスは Mixin B となります。

多重継承の問題点は Mix-in ですべて解決できるわけではありませんが、クラスの階層構造がすっきりとしてわかりやすくなることは間違いありません。Mix-in は多重継承を使いこなす優れた方法だと思います。

●enumerable

それでは Mix-in の例題として、クラス enumerable を作ってみましょう。enumerable は複数の要素を格納するコレクションクラスに高階関数 (メソッド) を Mix-in します。これは Ruby のモジュール (Mix-in 用のクラス) Enumerable を参考にしました。追加するメソッドを表 1 に示します。

プログラムは次のようになります。

リスト 5 : Mix-in 用のクラス enumerable

class virtual ['a] enumerable =
  object(self)
    method virtual begin0 : unit
    method virtual next : 'a option

    method find_if func =
      let rec _find = function
        None -> None
      | Some y when func y -> Some y
      | _ -> _find self#next
      in
      self#begin0;
      _find self#next

    method position_if func =
      let rec _position n = function
        None -> -1
      | Some y when func y -> n
      | _ -> _position (n + 1) self#next
      in
      self#begin0;
      _position 0 self#next

    method count_if func =
      let rec _count a = function
        None -> a
      | Some y when func y -> _count (a + 1) self#next
      | _ -> _count a self#next
      in
      self#begin0;
      _count 0 self#next

    ... 省略 ...
  end

クラス enumerable は Mix-in を前提としているので、インスタンス変数の定義は不要でメソッドだけを定義します。コレクションの要素を取り出す処理は仮想メソッド begin0 と next で行います。begin0 はコレクションから要素を取り出す準備を行います。実際に要素を取り出す処理は next で行います。next は要素を option に格納して返すことにします。要素がなくなったら None を返します。

あとは enumerable を Mix-in するクラスで、メソッド begin0 と next を具体化すればいいわけです。つまり、begin0 と next を定義さえすれば、どんなクラスでも enumberable を Mix-in することができるわけです。

member_if, position_if, count_if は簡単です。self#next で要素を取り出して関数 func に渡します。func が真を返す場合、member は要素を option に格納して返します。position_if は位置 n を返します。count_if は累積変数 a の値を +1 します。

●多相メソッド

次は、map, filter, fold を作ります。ここではプログラムを簡単にするため、map と filter は結果をリストに格納して返すことにします。filter は簡単ですが、map と fold はデータ型の指定が必要になります。プログラムは次のようになります。

リスト 6 : 多相メソッドの定義

method map : 'b.('a -> 'b) -> 'b list = fun func ->
  let rec _map = function
    None -> []
  | Some x -> func x :: _map self#next
  in
  self#begin0;
  _map self#next

method filter func =
  let rec _filter = function
    None -> []
  | Some x when func x -> x :: _filter self#next
  | _ -> _filter self#next
  in
  self#begin0;
  _filter self#next

method fold_left : 'b.('b -> 'a -> 'b) -> 'b -> 'b = fun func init ->
  let rec _fold a = function
    None -> a
  | Some x -> _fold (func a x) self#next
  in
  self#begin0;
  _fold init self#next

method iter : ('a -> unit) -> unit = fun func ->
  let rec _iter = function
      None -> ()
    | Some x -> (func x; _iter self#next)
  in
  self#begin0;
  _iter self#next

map, fold_left, iter の場合、データ型を指定しないでコンパイルすると、型推論により次に示すデータ型になります。

map  : ('a -> 'b) -> 'b list 
fold_left : ('b -> 'a -> 'b) -> 'b -> 'b
iter : ('a -> 'c) -> unit

map と fold_left の場合、型変数 'b が定義されていないため、コンパイルでエラーになります。iter の場合も型変数 'c が未定義のためエラーになります。クラスは型変数を指定することで「多相クラス」を定義することができました。メソッドの場合も型変数を指定することで「多相メソッド」を定義することができます。指定方法は次のように行います。

メソッド名 : 型変数. 型式

'a はクラスの型変数として指定されているので、メソッドの型で型変数 'b を指定すればいいわけです。iter の場合、引数 func の型を 'a -> unit にすれば大丈夫です。実際にクラス enumerable を定義すると、次のように表示されます。

class virtual ['a] enumerable :
  object
    method virtual begin0 : unit
    method count_if : ('a -> bool) -> int
    method filter : ('a -> bool) -> 'a list
    method find_if : ('a -> bool) -> 'a option
    method fold_left : ('b -> 'a -> 'b) -> 'b -> 'b
    method iter : ('a -> unit) -> unit
    method map : ('a -> 'b) -> 'b list
    method virtual next : 'a option
    method position_if : ('a -> bool) -> int
  end

map と fold は多相メソッドとして定義されていることがわかります。

ところで、map のようなメソッドにおいて、自分自身のクラスを返したい場合、多相メソッドとして定義できないことがあります。次の例を見てください。

# class ['a] foo (x : 'a) =
object(self)
  method get = x
  method map f = new foo (f self#get)
end

class ['a] foo :
  'a -> object method get : 'a method map : ('a -> 'a) -> 'a foo end

クラス foo のメソッド map はメソッド get の値に関数 f を適用し、その結果を foo のオブジェクトに格納して返します。この場合、OCaml はメソッドの型を ('a -> 'a) -> 'a foo と推論しています。map の型は ('a -> 'b) -> 'b foo のほうが便利なので、次のような型を指定したところ、コンパイルエラーになりました。

# class ['a] foo (x : 'a) =
object(self)
  method get_a = x
  method map : 'b.('a -> 'b) -> 'b foo = fun f -> new foo (f self#get)
end
Error: The universal type variable 'b cannot be generalized:
       it escapes its scope.

他のデータ型 (またはクラス) に格納して返すことは可能です。

# class ['a] foo (x : 'a) =
object(self)
  method get = x
  method map : 'b.('a -> 'b) -> 'b list = fun f -> [f self#get]
end
class ['a] foo :
  'a -> object method get : 'a method map : ('a -> 'b) -> 'b list end

このような場合、map はメソッドではなく関数として定義したほうが簡単です。

# class ['a] foo (x : 'a) = object method get = x end;;
class ['a] foo : 'a -> object method get : 'a end
# let map f xs = new foo (f xs#get);;
val map : ('a -> 'b) -> < get : 'a; .. > -> 'b foo = <fun>
# let a = new foo 10;;
val a : int foo = <obj>
# let b = map (fun x -> x * x) a;;
val b : int foo = <obj>
# b#get;;
- : int = 100
# let c = map (fun x -> x * x) (object method get = 20 end);;
val c : int foo = <obj>
# c#get;;
- : int = 400

foo のオブジェクトだけではなく、メソッド get を持つオブジェクトであれば何でも関数 map を使用することができます。

●リストクラス

次に、enumerable を Mix-in するクラスを作ります。ここでは簡単な例題として、リストクラス linkedlist を取り上げます。linkedlist のメソッドを表 2 に示します。

メソッド insert と delete_at は、リストを格納するインスタンス変数 content の値を書き換えます。つまり、これらのメソッドによりオブジェクトの状態が変化するわけです。このほかに enumerable で使うメソッド bigin0 と next を定義します。プログラムは次のようになります。

リスト 7 : linkedlist クラス

class ['a] linkedlist = 
  object
    inherit ['a] enumerable
    val mutable content = ([] : 'a list)
    val mutable iterator = ([] : 'a list)

    method insert n x =
      let rec _insert n ls =
         match (n, ls) with
           (0, _) -> x::ls
         | (_, []) -> raise (Invalid_argument "linkedlist.insert")
         | (_, y::ys) -> y :: _insert (n - 1) ys
      in
        content <- _insert n content

    method at n =
      let rec _at n ls =
        match (n, ls) with
          (0, x::_) -> x
        | (_, []) -> raise (Invalid_argument "linkedlist.at")
        | (_, _::xs) -> _at (n - 1) xs
      in
        _at n content

    method delete_at n =
      let rec _delete n ls =
        match (n, ls) with
          (0, _::xs) -> xs
        | (_, []) -> raise (Invalid_argument "linkedlist.delete")
        | (_, x::xs) -> x :: _delete (n - 1) xs
      in
        content <- _delete n content

    method is_empty = content = []

    method begin0 = iterator <- content
    method next =
      match iterator with
        [] -> None
      | x::xs -> iterator <- xs; Some x
  end

inherit で enumerable を Mix-in します。インスタンス変数 content はリストを格納します。iterator は begin0 と next で使います。begin0 は iterator に content の値をセットします。next は iterator の先頭要素を option に格納して返します。そして、iterator の値を先頭要素を取り除いたリストに更新します。これで、リストの要素を順番に取り出していくことができます。あとのメソッドは簡単なので説明は割愛いたします。

実際にクラス linkedlist を定義すると、次のように表示されます。

class ['a] linkedlist :
  object
    val mutable content : 'a list
    val mutable iterator : 'a list
    method at : int -> 'a
    method begin0 : unit
    method count_if : ('a -> bool) -> int
    method delete_at : int -> unit
    method filter : ('a -> bool) -> 'a list
    method find_if : ('a -> bool) -> 'a option
    method fold_left : ('b -> 'a -> 'b) -> 'b -> 'b
    method insert : int -> 'a -> unit
    method is_empty : bool
    method iter : ('a -> unit) -> unit
    method map : ('a -> 'b) -> 'b list
    method next : 'a option
    method position_if : ('a -> bool) -> int
  end

enumerable のメソッドが継承されていることがわかります。

●実行例

それでは実際に試してみましょう。

# let print x = x#iter (fun x -> print_int x; print_string " ");;
val print : < iter : (int -> unit) -> 'a; .. > -> 'a = 
# let a = new linkedlist;;
val a : '_a linkedlist = <obj>
# for i = 0 to 4 do a#insert i i done;;
- : unit = ()
# print a;;
0 1 2 3 4 - : unit = ()
# a#find_if (fun x -> x mod 2 = 1);;
- : int option = Some 1
# a#position_if (fun x -> x mod 2 = 0);;
- : int = 0
# a#count_if (fun x -> x mod 2 = 0);;
- : int = 3
# a#map (fun x -> x * x);;
- : int list = [0; 1; 4: 9; 16]
# a#filter (fun x -> x mod 2 = 0);;
- : int list = [0; 2; 4]
# a#fold_left (fun x y -> x + y) 0;;
- : int = 10

正常に動作していますね。また、次のように enumerable を Mix-in した集合クラスを定義することもできます。

リスト 8 : set に enumerable を Mix-in

class ['a] enumerable_set compare =
  object (self)
    inherit ['a] set compare
    inherit ['a] enumerable
    val mutable iterator = ([]: 'a list)
    method begin0 = iterator <- content
    method next =
      match iterator with
        [] -> None
      | x::xs -> iterator <- xs; Some x
  end

もちろん、set ではなく sorted_set を継承してもまったく問題ありません。

●クラスの関係

今まで説明したように、オブジェクトは関数とデータを一つにまとめたものです。オブジェクト指向プログラミングは、このオブジェクトを部品として扱います。実際には、クラス単位でプログラムを作るので、クラスの関係がとても重要になります。ここで、クラスの関係を表す is-a と has-a について簡単に説明します。

is-a 関係は X is a Y. の略で、「X は Y の一種である」という意味になります。X がサブクラスで Y をスーパークラスと考えると、is-a 関係は継承で表すことができます。たとえば、制限付きスタック fixed_stack は、格納する要素の個数が制限されていますがスタックの一種であることは明らかです。fixed_stack クラスは stack クラスを継承することで簡単に実装できましたが、それは stack との間に is-a 関係があるからです。

has-a 関係は X has a Y. の略で、「X は Y を持っている」という意味です。たとえば、車にはエンジンやタイヤがありますが、車とエンジンやタイヤに成り立つ関係が has-a です。車はエンジンやタイヤがないと走ることができませんね。このように、has-a 関係は「X が成立するのに欠かせない要素が Y である」という関係を表しています。

has-a 関係のほかに、is-implemented-using という関係があります。これは X is implemented using Y. の略で、「X は Y を使って実装される」という意味です。たとえば、スタックの場合、配列でも連結リストでも実装することが可能です。つまり、Y の種類によらず X を実現できる関係が is-implemented-using 関係なのです。

一般に、has-a 関係や is-implemented-using 関係は、クラス X のインスタンス変数にクラス Y のオブジェクト (インスタンス) を格納することで表します。これを「X は Y を包含している」といいます。「包含」とか「集約」と呼ぶ場合もあります。そして、これらの関係を表すのに継承を使ってはいけない、ということに注意してください。

たとえば、今回作成した連結リストクラス linkedlist を継承してスタックを作ることを考えてみましょう。PUSH は連結リストの先頭にデータを追加することで、POP は連結リストの先頭からデータを取り出すことで簡単に実現できます。しかし、連結リストを継承すると、ほかの操作も可能になります。スタックの途中にデータを追加したり、途中からデータを取り出すなど、スタックを破壊する危険な操作が可能になってしまいます。

また、クラスの関係を考えた場合、スタックと連結リストには is-a 関係は成り立ちません。ところが、継承を使うとプログラムの上でもスタックは連結リストの一種になってしまいます。継承は強力な機能ですが万能ではありません。クラス間の関係を考えて、適切に使うことが大切です。

●継承関係は必ずしも部分型にはならない

最後に、ちょっと難しい話題を取り上げます。OCaml の場合、型 A の部分型を B とすると、A と B に is-a 関係が成立すると考えられます。OCaml は継承を使わなくても部分型を生成することができるという特徴があります。ところが、クラスを継承したからといって、そのサブクラスが部分型になるとは限らないという特徴もあるのです。とくに、バイナリメソッドを持つクラスを継承すると、そのサブクラスはスーパークラスの部分型にはなりません。

簡単な例として、点を表すクラスを作ってみましょう。名前は point にしました。x 座標をインスタンス変数 x に、y 座標を変数 y に格納します。リスト 9 を見てください。

リスト 9 : point クラス

class point xi yi =
  object (self: 'self_type)
    val mutable x = xi
    val mutable y = yi

    method x = x
    method y = y
    (* 移動 *)
    method move dx dy =
      x <- x +. dx; y <- y +. dy
    (* 同じポイントか *)
    method equal (p: 'self_type) =
      x = p#x && y = p#y
  end

メソッド x, y は座標 x, y の値を返します。メソッド move はポイントを移動します。メソッド equal は 2 つのインスタンスが等しい座標かチェックします。実際に point を定義すると、次のように表示されます。

class point :
  float ->
  float ->
  object ('a)
    val mutable x : float
    val mutable y : float
    method equal : 'a -> bool
    method move : float -> float -> unit
    method x : float
    method y : float
  end

次に、point を継承して色付きのポイントを表す colored_point を定義します。次のリストを見てください。

リスト 10 : colored_point クラス

class colored_point xi yi (ci: int) =
  object (self: 'self_type)
    inherit point xi yi as super
    val mutable c = ci

    method color = c
    method equal (p: 'self_type) =
      super#equal p && c = p#color
  end

色は整数値で表します。その値はインスタンス変数 c にセットします。ここで、メソッド equal をオーバーライドしていることに注意してください。colored_point を定義すると、次のように表示されます。

class colored_point :
  float ->
  float ->
  int ->
  object ('a)
    val mutable c : int
    val mutable x : float
    val mutable y : float
    method color : int
    method equal : 'a -> bool
    method move : float -> float -> unit
    method x : float
    method y : float
  end

colored_point は point クラスを継承しているので、point の部分型になるように思います。ところが、colored_point は point の部分型にはなりません。たとえば、次のように型変換するとエラーになります。

# let a = new colored_point 0.0 0.0 0;;
val a : colored_point = <obj>
# let b = (a :> point);;
... エラーメッセージ (省略) ...

これはメソッド equal の型が point と colored_point では異なるためです。

point < equal: point -> bool; ... >
colored_point < equal: colored_point -> bool; ... >

メソッド equal の引数の型が、point と colored_point で異なっていますね。同名のメソッドでその型が異なっているため、colored_point は point の部分型にはならないのです。同様に、バイナリメソッドを持つクラス、たとえば set の場合も、set を継承したクラス sorted_set は set の部分型にはなりません。

住井英二郎先生の 数理科学的バグ撲滅方法論のすすめ 第4回　関数型言語とオブジェクト指向，およびOCamlの"O"について によると、『これは「inheritance is not subtyping」問題として広く知られている。』 とのことです。

このように、継承したからといって is-a 関係が成り立つとは限りません。M.Hiroi は「クラス＝型」で「継承関係＝部分型」という意識が強かったので、OCaml のオブジェクト指向には大変驚きました。あらためて、オブジェクト指向は奥が深いなあと思いました。

●プログラムリスト

リスト : クラス enumerable 

class virtual ['a] enumerable =
  object(self)
    method virtual begin0 : unit
    method virtual next : 'a option

    method find_if func =
      let rec _find = function
          None -> None
        | Some y when func y -> Some y
        | _ -> _find self#next
      in
      self#begin0;
      _find self#next

    method position_if func =
      let rec _position n = function
          None -> -1
        | Some y when func y -> n
        | _ -> _position (n + 1) self#next
      in
      self#begin0;
      _position 0 self#next

    method count_if func =
      let rec _count a = function
          None -> a
        | Some y when func y -> _count (a + 1) self#next
        | _ -> _count a self#next
      in
        self#begin0;
        _count 0 self#next

    method map : 'b.('a -> 'b) -> 'b list = fun func ->
      let rec _map = function
          None -> []
        | Some x -> func x :: _map self#next
      in
      self#begin0;
      _map self#next

    method filter func =
      let rec _filter = function
          None -> []
        | Some x when func x -> x :: _filter self#next
      | _ -> _filter self#next
      in
      self#begin0;
      _filter self#next

    method fold_left : 'b.('b -> 'a -> 'b) -> 'b -> 'b = fun func init ->
      let rec _fold a = function
        None -> a
      | Some x -> _fold (func a x) self#next
      in
      self#begin0;
      _fold init self#next

    method iter : ('a -> unit) -> unit = fun func ->
      let rec _iter = function
          None -> ()
        | Some x -> (func x; _iter self#next)
      in
      self#begin0;
      _iter self#next
  end

●問題

前回の問題で作成した可変長配列クラス arraylist に enumerable を Mix-in してください。

●解答

リスト : 可変長配列クラス

exception Empty
exception Out_of_range

class ['a] arraylist init_size (init_value : 'a) =
object
  inherit ['a] enumerable
  val mutable buff = Array.make init_size init_value
  val mutable top = 0
  val mutable idx = 0

  method push x =
    if top >= Array.length buff then
      let newbuff = Array.make (2 * Array.length buff) init_value in
      Array.blit buff 0 newbuff 0 (Array.length buff);
      buff <- newbuff
    else ();
    buff.(top) <- x;
    top <- top + 1

  method pop =
    if top = 0 then raise Empty
    else (top <- top - 1; buff.(top))

  method peek =
    if top = 0 then raise Empty
    else buff.(top - 1)

  method get i =
    if i < 0 || i >= top then raise Out_of_range
    else buff.(i)

  method set i x =
    if i < 0 || i >= top then raise Out_of_range
    else buff.(i) <- x

  method length = top

  method begin0 = idx <- 0
  method next =
    if idx >= top then None
    else (idx <- idx + 1; Some buff.(idx - 1))
end

exception Empty
exception Out_of_range
class ['a] arraylist :
  int ->
  'a ->
  object
    val mutable buff : 'a array
    val mutable idx : int
    val mutable top : int
    method begin0 : unit
    method count_if : ('a -> bool) -> int
    method filter : ('a -> bool) -> 'a list
    method find_if : ('a -> bool) -> 'a option
    method fold_left : ('b -> 'a -> 'b) -> 'b -> 'b
    method get : int -> 'a
    method iter : ('a -> unit) -> unit
    method length : int
    method map : ('a -> 'b) -> 'b list
    method next : 'a option
    method peek : 'a
    method pop : 'a
    method position_if : ('a -> bool) -> int
    method push : 'a -> unit
    method set : int -> 'a -> unit
  end

# let a = new arraylist 8 0;;
val a : int arraylist = 
# for i = 1 to 8 do a#push i done;;
- : unit = ()
# a#length;;
- : int = 8
# a#iter (fun x -> print_int x; print_newline());;
1
2
3
4
5
6
7
8
- : unit = ()
# a#find_if (fun x -> x > 5);;
- : int option = Some 6
# a#find_if (fun x -> x > 10);;
- : int option = None
# a#position_if (fun x -> x > 5);;
- : int = 5
# a#position_if (fun x -> x > 10);;
- : int = -1
# a#count_if (fun x -> x > 5);;
- : int = 3
# a#count_if (fun x -> x < 5);;
- : int = 4
# a#map (fun x -> x * x);;
- : int list = [1; 4; 9; 16; 25; 36; 49; 64]
# a#filter (fun x -> x mod 2 = 0);;
- : int list = [2; 4; 6; 8]
# a#fold_left (+) 0;;
- : int = 36