お気楽 F# プログラミング超入門

オブジェクト指向

プログラミングに興味のある方ならば、「オブジェクト指向」という言葉は聞いたことがあると思います。よく使われているオブジェクト指向言語に Java や C++ があります。また、Perl, Python, Ruby などのスクリプト言語や .NET (C#, F#) でもオブジェクト指向をサポートしています。

多くの言語でサポートされている「オブジェクト指向」ですが、関数型言語では Common Lisp の CLOS (Common Lisp Object System) が有名でしょう。CLOS は Java, C++ などのポピュラーなオブジェクト指向とはちょっと違っていて、興味深い機能がたくさんあります。F# のベースになった OCaml は "Objective Caml" の略なので、オブジェクト指向はサポートしているのですが、一般的なオブジェクト指向とは異なるところが多くあります。それと、OCaml と F# ではクラスの構文が異なるので注意してください。

F# 初心者である M.Hiroi が F# のオブジェクト指向を説明するのは無謀なことだとは思いますが、簡単なところから少しずつ勉強していきましょう。まず最初に、一般的なオブジェクト指向について簡単に説明します。

●オブジェクトとは？

プログラムを作る場合、全体を小さな処理に分割して一つ一つの処理を作成し、それらを組み合わせて全体のプログラムを完成させます。このとき、基本的な部品となるのが関数です。つまり、処理を関数単位で分割して、それらを組み合わせてプログラムを作るわけです。もともと関数の役割は、入力されたデータを処理してその結果を返すことです。つまり、関数は機能を表しているのです。このため、全体を小さな処理に分割するにしても、機能単位で行われることが普通です。

オブジェクト指向プログラミングでは、関数ではなく「オブジェクト (object)」を部品として扱います。たとえば、えんぴつを考えてみましょう。えんぴつには、色、長さ、固さ、などいろいろな性質があります。そして、えんぴつを使って文字を書いたり、絵を描いたりすることができます。プログラムでは、このような性質をデータで表し、機能を関数で表すことになります。そしてオブジェクトとは、このデータと関数を結び付けたものなのです。

今までのプログラミング言語では、データと関数を別々に定義するため、それをひとつのオブジェクトとして表すことができません。えんぴつで文字を書くにも、えんぴつの種類をチェックして文字を書くようにプログラムしなければいけません。ところが、オブジェクトはデータと関数を結び付けたものなので、自分がなにをしたらよいかわかっています。えんぴつオブジェクトに文字を書けと命じれば、それが赤えんぴつのオブジェクトであれば文字は赤に、黒えんぴつのオブジェクトであれば黒い文字になるのです。

このように、オブジェクトはデータと関数をひとつにまとめたものです。従来のプログラミングが全体を機能単位で分割するのに対し、オブジェクト指向プログラミングでは全体をオブジェクト単位に分割して、それを組み合わせることでプログラムを作成します。

ところで、データと関数を結び付けることは、従来のプログラミング言語でも可能です。オブジェクト指向はプログラミングの考え方の一つであり、C++ のようなオブジェクト指向言語を使わなくても、たとえばＣ言語でもその考え方に従ってプログラムを作れば、オブジェクト指向プログラミングになります。

実際、オブジェクト指向には様々な考え方があり、いろいろなオブジェクト指向言語が存在します。ですが、データと関数を一つにまとめたものをオブジェクトとして扱うという基本的な考え方は、オブジェクト指向言語の元祖と言われる Smalltalk でも、Java, C++, C#, F# でも同じです。

●クラスとインスタンス

次は、一般的なオブジェクト指向機能について簡単に説明します。

「クラス (class)」はオブジェクトの振る舞いを定義したものです。ここでデータを格納するための変数や、それを操作する関数が定義されます。この変数を「メンバ変数」とか「インスタンス変数」といい、関数を「メソッド (method)」といいます。メソッドはあとで説明します。

クラスはオブジェクトの設計図にあたるもので、オブジェクトの「雛形」と呼ぶこともあります。クラスはオブジェクトの振る舞いを定義するだけで、アクセスできる実体はなにも生み出していない、ということに注意してください。

このクラスから実体として作り出されるのが「インスタンス (instance)」です。このインスタンスを「オブジェクト」と考えてください。インスタンスを生成する方法は、当然ですがプログラミング言語によって違います。たとえば C++ や Java は new を使います。図 1 を見てください。


               図 1 : クラスとインスタンスの関係

クラスはオブジェクトの定義を表すものですから、Foo というクラスはひとつしかありません。これに対し、インスタンスはクラスから生み出されるオブジェクトです。たとえば、クラス Foo に new を適用することで、いくつでもインスタンスを生み出すことができるのです。クラスは設計図であり、それに従って作られるオブジェクトがインスタンスと考えるとわかりやすいでしょう。

●メソッド

メソッドはオブジェクトと結びついた関数です。オブジェクト指向プログラミングでは、ほかの関数から直接オブジェクトを操作することはせず、メソッドを呼び出すことで行います。メソッドは、クラスが異なっていれば同じ名前のメソッドを定義することができます。たとえば、クラス Foo1 にメソッド bar() が定義されていても、クラス Foo2 に同名のメソッド bar() を定義することができます。

そして、ここからが重要なのですが、あるオブジェクトに対してメソッド bar() を呼び出した場合、それが Foo1 から作られたオブジェクトであれば、Foo1 で定義された bar() が実行され、Foo2 から作られたオブジェクトであれば、Foo2 で定義された bar() が実行されるのです。

このように、オブジェクトが属するクラスによって、実行されるメソッドが異なるのです。この機能を「ポリモーフィズム(polymorphism)」と呼びます。これにより、オブジェクトは自分が行うべき適切な処理を実行できるわけです。

クラス、インスタンス、メソッドの関係は図 2 のようになります。


         図 2 : クラス、インスタンス、メソッドの関係

クラスという設計図が中心にあり、そこからインスタンスが生み出され、メソッドを使ってインスタンスを操作する、という関係になります。

●F# のクラス

さて、一般的な話はここまでにして、F# のオブジェクト指向機能に目を向けてみましょう。F# は type 宣言でクラスを定義します。クラスの基本的な構文を示します。

type class_name (parameter-list) = class ... end

type の次にクラス名を指定し、その後ろにインスタンスを生成するときに使用する仮引数と型をタプルで指定します。= の右辺 class ... end でインスタンス変数やメソッドを定義します。軽量構文を使うと、class と end を省略することができます。

一番簡単なクラス定義を示しましょう。次の例を見てください。

> type Foo() = class end;;
type Foo =
  new: unit -> Foo

一般的なオブジェクト指向言語では、クラス名を英大文字から始めることが多いので、本稿でもそれに従うことにします。OCaml は F# とは異なり、英大文字から始まる名前はコンストラクタとして認識されるので、クラス名は英小文字から始めます。ご注意くださいませ。

Foo はクラス名しかありませんが、これでも立派なクラスなのです。次の例を見てください。

> let a = new Foo();;
val a: Foo

F# は次の形式でインスタンスを生成します。

new クラス名(引数, ...)

インスタンスを生成するとき、引数を指定することができます。これはあとで説明します。

●アクセス制御

F# は public, internal, private というアクセス制御指定子を使ってアクセス制御を行うことができます。public はどのクラス (またはモジュール) からでもアクセスすることできます。private は同じクラス (またはモジュール) の中でしかアクセスすることができません。internal はちょっと難しくて、同じアセンブリであればアクセスすることができます。

ここでいうアセンブリとは、ファイルをコンパイルして生成される実行形式ファイル (.exe) やダイナミックリンクライブラリ (.dll) のことです。F# (.NET) は複数のファイルをコンパイルして、一つのアセンブリを生成することができます。internal の場合、同一ファイル内でなくても同じアセンブリ内であれば、異なるクラス (またはモジュール) からアクセスすることができます。

●インスタンス変数とメソッドの定義

F# の場合、インスタンス変数は let で、メソッドは member で定義します。

let [mutable] 変数名 = 初期値
member 自己修飾子.メソッド名 引数 ... = 式

let によるインスタンス変数のアクセス制御は private に設定されます。クラスの外からアクセスすることはできません。また、名前の前に mutable を付けると値を書き換えることができます。インスタンス変数の書き換えは演算子 <- で行います。

変数 <- 式

メソッドの定義は let の代わりにキーワード member を使います。自己修飾子はメソッドを呼び出したインスタンスを表す変数になります。他のプログラミング言語では this とか self などと呼ばれています。F# では自由に名前を付けることができます。

それでは、簡単な例を示しましょう。

リスト : インスタンス変数とメソッドの定義

type Foo() =
  let mutable a = 10
  member this.geta () = a
  member this.seta x = a <- x

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

type Foo =
  new: unit -> Foo
  member geta: unit -> int
  member seta: x: int -> unit

メソッドの呼び出しは次の形式で行います。

インスタンス.メソッド名(引数, ...)

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

> let x = new Foo();;
val x: Foo

> x.geta();;
val it: int = 10

> x.seta(100);;
val it: unit = ()

> x.geta();;
val it: int = 100

このように、メソッドを呼び出してインスタンス変数の値を取得したり、値を書き換えることができます。

●プロパティ

F# は C# と同様に「プロパティ (property)」を定義することができます。プロパティはインスタンス変数にアクセスするためのメソッドのことで、クラス外部から見るとインスタンス変数に直接アクセスしているかのように振る舞います。

プロパティの基本的な構文を以下に示します。

1. getter と setter の設定
member 自己修飾子.プロパティ名 with get() = 式
                             and set(value) = 式

2. getter のみ
member 自己修飾子.プロパティ名 = 式

3. setter のみ
member 自己修飾子.プロパティ with set(value) = 式

プロパティ名は英大文字から始めます。インスタンス.プロパティ名で値を取得し、インスタンス.プロパティ名 <- value で値を更新します。簡単例を示しましょう。

リスト : プロパティの定義

type Bar() =
  let mutable a = 10
  member this.A with get() = a
                and set(x) = a <- x

type Bar =
  new: unit -> Bar
  member A: int

> let b = new Bar();;
val b: Bar

> b.A;;
val it: int = 10

> b.A <- 100;;
val it: unit = ()

> b.A;;
val it: int = 100

getter と setter はキーワード val を使って自動生成することができます。

1. getter と setter の設定
member val プロパティ名 = 初期値 with get, set

2. getter のみ
member val プロパティ名 = 初期値

この場合、let でインスタンス変数を宣言する必要はありません。値を格納するインスタンス変数も自動的に生成されます。簡単な例を示しましょう。

リスト : プロパティの自動設定

type Baz() =
  member val A = 10 with get, set

type Baz =
  new: unit -> Baz
  member A: int

> let c = new Baz();;
val c: Baz

> c.A;;
val it: int = 10

> c.A <- 100;;
val it: unit = ()

> c.A;;
val it: int = 100

●コンストラクタ

F# は new を使ってインスタンスを生成しますが、このときインスタンス変数の初期値を指定できると便利です。次の構文を見てください。

type クラス名 (引数1: 型1, 引数2: 型2, ...) = class
  let ...          // let 束縛
    ...

  do               // do 束縛
    ...
    ...
  // ここまでがプライマリコンストラクタ
  member ...
  ...
end

一般に、インスタンスを生成するときに呼び出すメソッドを「コンストラクタ (constructor)」といいます。コンストラクタは「生成関数」とか「構築子」と呼ばれることがあります。F# の場合、コンストラクタに渡す引数はクラス名と = の間のタプルで記述します。これを「プライマリコンストラクタ」といいます。

プライマリコンストラクタは、クラスに定義されている let 束縛と do 束縛を実行します。let 束縛はインスタンス変数の生成と初期化を行います。do 束縛は do の中に書かれている式を順番に実行します。これはインスタンスを生成するとき、副作用を伴うような処理を実行するときに便利です。let 束縛と do 束縛はコンストラクタの引数を参照することができます。そのあとにキーワード member を使ってメソッドを定義します。let 束縛と do 束縛はキーワード member よりも前に定義してください。

たとえば、クラス Foo に整数値を渡す場合は次のようになります。

リスト : 引数の指定方法

type Foo (init: int) =
  let mutable a = init
  do printfn "create Foo(%d)" init
  member this.A with get() = a
                and set(x) = a <- x

引数 init でインスタンス変数の値を初期化します。init の型は int に指定します。このプログラムでは引数のデータ型を指定しましたが、F# はクラスに型変数を渡すことで多相的なクラスを定義することができます。これはあとで説明します。

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

type Foo =
  new: init: int -> Foo
  member A: int

あとは new でインスタンスを生成するときに値を渡すだけです。

> let a = new Foo(100);;
create Foo(100)
val a: Foo

> a.A;;
val it: int = 100

> let b = new Foo(200);;
create Foo(200)
val b: Foo

> b.A;;
val it: int = 200

> a.A <- 1000;;
val it: unit = ()

> a.A;;
val it: int = 1000

> b.A;;
val it: int = 200

インスタンスを生成するたびに do 束縛の式 printfn "..." が実行されることがわかります。

●メソッドの多重定義

F# は同じクラス内で同名のメソッドを複数定義することができます。これを「多重定義 (overload)」といいます。ただし、引数の型、個数、並び方などが異なる必要があります。これらがまったく同じメソッドを多重定義することはできません。コンストラクタもメソッドなので多重定義することができます。

コンストラクタを多重定義するときはメソッド new() を使います。

new(型1: 仮引数1, ...) =
  式1
  ...
  then
    式N
    ...

プライマリコンストラクタが定義されている場合、多重定義した new() からプライマリコンストラクタを呼び出してください。それから、new() では do 束縛のかわりにキーワード then を使います。then 節に定義された式を順番に実行します。

簡単な例を示しましょう。

リスト : コンストラクタの多重定義

type Foo (init: int) =
  let mutable a = init
  do printfn "create Foo(%d)" init
  member this.A with get() = a
                and set(x) = a <- x
  new() = Foo(0) then printfn "create Foo()"

type Foo =
  new: unit -> Foo + 1 オーバーロード
  member A: int

> new Foo(10);;
create Foo(10)
val it: Foo = FSI_0031+Foo {A = 10;}

> new Foo();;
create Foo(0)
create Foo()
val it: Foo = FSI_0031+Foo {A = 0;}

プライマリコンストラクタの do 束縛を実行してから、new() の then 節が実行されることが分かります。

●キーワード val

インスタンス変数はキーワード val を使って定義することもできます。

val [ mutable ] [ access-modifier ] 変数名 : 型名

val は変数を宣言するだけで初期化は行われません。val で宣言された変数を「明示的なフィールド」と呼びます。let のアクセス制御は private になりますが、val のアクセス制御は access-modifier で指定することができます。省略した場合は public になります。

プライマリコンストラクタで val を使うときは DefaultValue 属性と mutable が必要になります。

[<DefaultValue>] val mutable 変数名 : 型名

[<...>] は属性を指定する構文です。DefaultValue はフィールドがゼロ初期化されることを示します。ゼロ初期化は、数値であれば 0 や 0.0 に、参照型であれば null に初期化されます。なお、val で定義されたインスタンス変数にアクセスする場合、let 束縛のように変数名だけでアクセスすることはできません。同じクラス内であっても、インスタンス + "." + 変数名でアクセスしてください。

簡単な例を示しましょう。

リスト : val によるインスタンス変数の宣言

type Foo() =
  [<DefaultValue>] val mutable a : int
  [<DefaultValue>] val mutable b : float
  [<DefaultValue>] val mutable c : string
  member this.print() = printfn "(%d, %f, %s)" this.a this.b this.c

type Foo =
  new: unit -> Foo
  val mutable a: int
  val mutable b: float
  val mutable c: string
  member print: unit -> unit

> let x = new Foo();;
val x: Foo

> x.a;;
val it: int = 0

> x.b;;
val it: float = 0.0

> x.c;;
val it: string = <null>

> x.print();;
(0, 0.000000, )
val it: unit = ()

プライマリコンストラクタが定義されていない場合、DefaultValue 属性と mutable はなくてもかまいませんが、val で宣言した変数をメソッド new() で明示的に初期化する必要があります。簡単な例を示しましょう。

リスト : val によるインスタンス変数の宣言 (2)

type Bar = class
  val a : int
  val b : float
  val c : string
  new (x, y, z) = {a = x; b = y; c = z}
  member this.print() = printfn "(%d, %f, %s)" this.a this.b this.c
end

インスタンス変数の初期化にはレコードを生成するときと同じ構文を使います。

type Bar =
  new: x: int * y: float * z: string -> Bar
  val a: int
  val b: float
  val c: string
  member print: unit -> unit

> let y = new Bar(1, 1.234, "bar");;
val y: Bar

> y.a;;
val it: int = 1

> y.b;;
val it: float = 1.234

> y.c;;
val it: string = "bar"

> y.print();;
(1, 1.234000, bar)
val it: unit = ()

●Point クラス

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

リスト : Point クラス

type Point(x0: float, y0: float) =
  let x = x0
  let y = y0
  member this.X with get() = x
  member this.Y with get() = y
  // 距離を求める
  member this.distance(p: Point) =
    let dx = x - p.X
    let dy = y - p.Y
    sqrt(dx * dx + dy * dy)

// 別解 (プロパティの自動設定)
type Point(x0: float, y0: float) =
  member val X = x0 
  member val Y = y0
  // 距離を求める
  member this.distance(p: Point) =
    let dx = this.X - p.X
    let dy = this.Y - p.Y
    sqrt(dx * dx + dy * dy)

メソッド distance() は Point クラスのインスタンス p を受け取り、その距離を計算します。sqrt() は平方根を求める関数です。別解はプロパティの自動設定を使う方法です。プロパティの場合、その値を求めるには対象となるインスタンスが必要になります。メソッドには自己修飾子 this が定義されているので、this.X, this.Y とすることで自分自身の X と Y の値を求めることができます。

あとは Point のインスタンスを生成して、変数 p0, p1 にセットして p0.distance(p1) で p0 と p1 の距離を計算します。実行結果は次のようになります。

type Point =
  new: x0: float * y0: float -> Point
  member distance: p: Point -> float
  member X: float
  member Y: float

> let p0 = new Point(0.0, 0.0);;
val p0: Point

> let p1 = new Point(1.0, 1.0);;
val p1: Point

> p0.distance(p1);;
val it: float = 1.414213562

ここで、インスタンスメソッドの呼び出しは、インスタンスによって適切なメソッドが選択されることに注意してください。たとえば、3 次元の座標を表す Point3D クラスを考えてみましょう。次のリストを見てください。

リスト : Point3D クラス

type Point3D(x0: float, y0: float, z0: float) =
  member val X = x0 
  member val Y = y0
  member val Z = z0
  // 距離を求める
  member this.distance(p: Point3D) =
    let dx = this.X - p.X
    let dy = this.Y - p.Y
    let dz = this.Z - p.Z
    sqrt(dx * dx + dy * dy + dz * dz)

クラス Point3D は Point を 3 次元に拡張しただけです。Point でも Point3D でも距離を計算するメソッド distance() が定義されていることに注目してください。それでは、メソッド distance() を呼び出してみましょう。

type Point3D =
  new: x0: float * y0: float * z0: float -> Point3D
  member distance: p: Point3D -> float
  member X: float
  member Y: float
  member Z: float

> let p2 = new Point3D(0.0, 0.0, 0.0);;
val p2: Point3D

> let p3 = new Point3D(10.0, 10.0, 10.0);;
val p3: Point3D

> p2.distance(p3);;
val it: float = 17.32050808

> p3.distance(p2);;
val it: float = 17.32050808

> p1.distance(p0);;
val it: float = 1.414213562

ドットの左側のインスタンス p1, p2, p3 によって適切なメソッドが呼び出され、ポリモーフィズムが働いているようにみえます。Python や Ruby などのように、変数を使用するときデータ型の宣言が不要なプログラミング言語を「動的型付け言語」といい、Ｃ/Ｃ++や Java などのように変数を使用するときデータ型の宣言が必要なプログラミング言語を「静的型付け言語」といいます。F# や OCaml も静的型付け言語です。

たとえば Ruby の場合、p1.distance(p3) で呼び出されるメソッド distance() は、プログラムを実行するとき変数 p1 に格納されているオブジェクトの型 (クラス) によって決定されます。p1 が Point のインスタンスであれば、Point で定義されたメソッド distance() が呼び出されます。つまり、動的型付け言語のメソッド呼び出しはポリモーフィズムが働いている、と考えることができます。

これに対し、Java や F# などの静的型付け言語は、コンパイルの時点で呼び出すメソッドを可能な限り決定します。p1.distance(p2) の呼び出しは Point クラスのメソッドで、p3.distance(p4) は Point3D クラスのメソッドと決めることが可能です。この場合、動的型付け言語のようなポリモーフィズムは働いていませんが、オブジェクトのクラスによって呼び出すメソッドが決定される、ということにかわりはありません。

Java や F# でプログラムの実行時にポリモーフィズムを働かせるには「継承」もしくは「インターフェース」という機能を使います。これは次回以降で説明します。

●ジェネリッククラス

クラスはバリアントやレコードと同様に、型変数を使って多相的なデータ構造を定義することができます。OCaml の場合、これを「多相クラス (polymorphic class)」といいますが、F# では「ジェネリッククラス」といいます。型変数は次のように指定します。

type クラス名<型変数1, ...> (型1: 引数1, ...) = class ... end

クラス名の後ろの < ... > の中に型変数を指定します。これで、コンストラクタの引数や class ... end の中で型変数を参照することができます。

それでは簡単な例題として、2 つのデータを格納するクラス Pair を作ってみましょう。F# にはタプルがあるので、このようなクラスを作る必要はありませんが、クラスでも簡単に定義することができます。

リスト : Pair クラス

type Pair<'a, 'b>(x: 'a, y: 'b) =
  member val Fst = x with get, set
  member val Snd = y with get, set

今回はクラスを使って実装するので、mutable なデータ構造にしてみました。簡単な実行例を示します。

type Pair<'a,'b> =
  new: x: 'a * y: 'b -> Pair<'a,'b>
  member Fst: 'a
  member Snd: 'b

> let a = new Pair<string,int>("foo", 123);;
val a: Pair<string,int>

> a.Fst;;
val it: string = "foo"

> a.Snd;;
val it: int = 123

> a.Fst <- "bar";;
val it: unit = ()

> a.Snd <- 456;;
val it: unit = ()

> a.Fst;;
val it: string = "bar"

> a.Snd;;
val it: int = 456

もう一つ簡単な例題として、スタックを作ってみましょう。クラスでスタックを定義すると次のようになります。

リスト : スタック (stack2.fsx)

// 例外
exception Empty

// クラス定義
type Stack<'a> () =
  // データを格納するリスト
  let mutable content: 'a list = []

  // データを追加
  member this.push x =
    content <- x::content

  // データの削除
  member this.pop () =
    match content with
      [] -> raise Empty
    | x::xs -> content <- xs; x

  //データの取得
  member this.top () =
    match content with
      [] -> raise Empty
    | x::_ -> x

  // スタックは空か *)
  member this.is_empty () = List.isEmpty content

データはインスタンス変数 content のリストに格納します。ここでクラスに渡された型変数 'a を使ってデータ型を 'a list に指定します。データ型を指定しなかったり、型変数を渡さずに 'a list と指定するとコンパイルでエラーになります。

メソッドの動作は拙作のページモジュールで作成した「参照型データを使ったスタックの実装」と同じです。メソッド push は content の先頭にデータ x を追加します。メソッド pop は content の先頭の要素を取り除いて、その値を返します。メソッド top は content の先頭の要素を返します。メソッド is_empty は content が空リストであれば true を返します。

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

> #load "stack2.fsx";;
[読み込み中 /home/mhiroi/fsharp/stack2.fsx]
namespace FSI_0024
  exception Empty
  type Stack<'a> =
    new: unit -> Stack<'a>
    member is_empty: unit -> bool
    member pop: unit -> 'a
    member push: x: 'a -> unit
    member top: unit -> 'a

簡単な実行例を示します。

> open Stack2;;
> let a = new Stack<int>();;
val a: Stack<int>

> for i = 0 to 9 do a.push i done;;
val it: unit = ()

> a.is_empty();;
val it: bool = false

> a.top();;
val it: int = 9

> while not (a.is_empty()) do printfn "%d " (a.pop()) done;;
9
8
7
6
5
4
3
2
1
0
val it: unit = ()

このように、型変数を渡すことでジェネリッククラスを定義することができます。

●private メソッド

もう一つ簡単な例としてキューを作ってみましょう。拙作のページモジュールで作成した「キュー」をクラスを使って実装します。次のリストを見てください。

リスト : キュー (queue1.fsx)

exception Empty

type Queue<'a>() =
    let mutable front : 'a list = []
    let mutable rear  : 'a list = []

    //データの移動
    member private this.move () =
      front <- (List.rev rear); rear <- []

    // データの追加
    member this.enqueue x = rear <- x :: rear

    //データの削除
    member this.dequeue () =
      if List.isEmpty front then this.move();
      match front with
        [] -> raise Empty
      | x::xs -> front <- xs; x

    // データの取得
    member this.top () =
      if List.isEmpty front then this.move();
      match front with
        [] -> raise Empty
      | x::_ -> x

    //キューは空か
    member this.is_empty () =
      (List.isEmpty front) && (List.isEmpty rear)

インスタンス変数 front と rear にデータを格納するリストをセットします。このプログラムは front と rear の値を書き換えることで動作します。データの追加は簡単ですね。メソッド enqueue は引数 x を rear の先頭に追加するだけです。

メソッド dequeue と top は、rear のデータを front に移動するメソッド move を呼び出すと簡単に定義できます。メソッドから同じクラスのメソッドを呼び出す場合、メソッドを呼び出したインスタンスが必要になります。F# の場合、メソッドには自己修飾子があるので、それを用いてメソッドを呼び出すことができます。今回は変数名に this を使っています。this.move() とすれば、メソッド move を呼び出して、rear のデータを front に移動することができます。

ここで move の前に付いているキーワード private に注目してください。move はクラス内部のメソッドから呼び出される作業用のメソッドです。もしも外部から move を呼び出すことができると、キューの状態を破壊することになるのでとても危険です。このような場合、private をつけることでメソッドを外部から隠蔽することができます。

dequeue と top は front が空リストであれば move を呼び出してデータを移動します。そして、dequeue はキューから先頭の要素を取り除き、top は先頭の要素を返します。is_empty はキューが空の場合は true を返します。

実際にキューを定義すると次のように表示されます。

> #load "queue1.fsx";;
[読み込み中 /home/mhiroi/fsharp/queue1.fsx]
namespace FSI_0028
  exception Empty
  type Queue<'a> =
    new: unit -> Queue<'a>
    member dequeue: unit -> 'a
    member enqueue: x: 'a -> unit
    member is_empty: unit -> bool
    member private move: unit -> unit
    member top: unit -> 'a

メソッド move のデータ型が表示されていますが、private が付いているので外部から呼び出すことはできません。

それでは簡単な実行例を示します。

> open Queue1;;
> let a = new Queue<int>();;
val a: Queue<int>

> for i = 0 to 9 do a.enqueue i done;;
val it: unit = ()

> a.is_empty();;
val it: bool = false

> while not (a.is_empty()) do printfn "%d" (a.dequeue()) done;;
0
1
2
3
4
5
6
7
8
9
val it: unit = ()

正常に動作していますね。

●問題

可変長の配列を表すクラス ArrayList を定義してください。

new ArrayList<'a>(init_size: int, init_value: 'a)

初期サイズ init_size で初期値が init_value の ArrayList を作成する
返り値は空の ArrayList (要素数 = 0)
ArrayList に要素を追加できるのはメソッド push だけ
添字が 0 - (要素数 - 1) の範囲であればメソッド get, set でアクセスできる

a.get i, 配列 a の i 番目の要素を求める
a.set(i, x), 配列 a の i 番目の要素を x に書き換える
a.push x, 配列 a の末尾に x を追加

配列 a が満杯の場合は大きさを増やす

a.pop (), 末尾の要素を取り出す

配列 a の大きさは縮小しないこととする

a.peek (), 配列 a の末尾要素を参照する
a.length (), 配列 a の要素数を求める

●解答

リスト : 可変長配列クラス (arraylist.fsx)

module Mylib

exception Empty
exception Out_of_range

type ArrayList<'a>(init_size: int, init_value: 'a) =
  let mutable buff = Array.create init_size init_value
  let mutable top = 0

  member this.push x =
    let len = Array.length buff
    if top >= len then
      let newbuff = Array.create (len * 2) init_value
      newbuff[0..(len-1)] <- buff
      buff <- newbuff
    else ()
    buff.[top] <- x
    top <- top + 1

  member this.pop () =
    if top = 0 then raise Empty
    else (
      top <- top - 1
      buff.[top]
    )

  member this.peek () =
    if top = 0 then raise Empty
    else buff.[top - 1]

  member this.get x =
    if x < 0 || x >= top then raise Out_of_range
    else buff.[x]

  member this.set x v =
    if x < 0 || x >= top then raise Out_of_range
    else buff.[x] <- v

  member this.length () = top

> #load "arraylist.fsx";;
[読み込み中 /home/mhiroi/fsharp/arraylist.fsx]
namespace FSI_0002
  exception Empty
  exception Out_of_range
  type ArrayList<'a> =
    new: init_size: int * init_value: 'a -> ArrayList<'a>
    member get: x: int -> 'a
    member length: unit -> int
    member peek: unit -> 'a
    member pop: unit -> 'a
    member push: x: 'a -> unit
    member set: x: int -> v: 'a -> unit

インスタンス変数 buff に配列本体を、インスタンス変数 top はスタックトップの位置を表します。これは配列の要素数と同じで、0 に初期化します。メソッド push は x を追加するとき、buff の大きさと top を比較します。同じ値であれば満杯なので x を追加することはできません。大きさが 2 倍の配列を生成して変数 newbuff にセットします。それから、buff の要素を newbuff にコピーします。これは配列のスライス操作を使うと簡単です。

1. ary.[s .. e] => newAry
2. ary1.[s1 .. e1] <- ary2.[s2 .. e2]

1 は ary の s 番目から e 番目の要素を格納した新しい配列 newAry を返します。つまり、ary の部分配列を取り出す働きをします。2. は ary1 の s1 番目から e1 番目の要素を、ary2 の s2 番目から e2 番目の要素に書き換えます。要素数が同じでないとエラーになります。

簡単な使用例を示しましょう。

> let a = [|1 .. 5|];;
val a: int[] = [|1; 2; 3; 4; 5|]

> let b = Array.create 10 0;;
val b: int[] = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]

> b[0..4] <- a;;
val it: unit = ()

> b;;
val it: int[] = [|1; 2; 3; 4; 5; 0; 0; 0; 0; 0|]

> b[5..9] <- a;;
val it: unit = ()

> b;;
val it: int[] = [|1; 2; 3; 4; 5; 1; 2; 3; 4; 5|]

あとは newbuff を buff にセットし、top の位置に x を書き込んでから top の値を +1 します。

メソッド pop は top の値を -1 してから、buff.[top] の値を返します。メソッド peek は buff.[top - 1] の値を返します。top が 0 の場合、配列は空なので例外 Empty を送出します。メソッド get, set は簡単ですね。添字 x が範囲外であれば例外 Out_of_range を送出します。メソッド length は top の値を返すだけです。

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

> open Mylib;;
> let a = new ArrayList(4, 0);;
val a: ArrayList

> a.length();;
val it: int = 0

> for i = 1 to 8 do a.push i done;;
val it: unit = ()

> a.length();;
val it: int = 8

> for i = 0 to 7 do printfn "%d" (a.get(i)) done;;
1
2
3
4
5
6
7
8
val it: unit = ()

> for i = 0 to 7 do a.set i (a.get(i) * 10) done;;
val it: unit = ()

> for i = 0 to 7 do printfn "%d" (a.get(i)) done;;
10
20
30
40
50
60
70
80
val it: unit = ()

> for i = 0 to 7 do printfn "%d" (a.pop()) done;;
80
70
60
50
40
30
20
10
val it: unit = ()

> a.length();;
val it: int = 0

> a.get 0;;
FSI_0002.Mylib+Out_of_range: Exception of type 'FSI_0002.Mylib+Out_of_range' was thrown.
... 略 ...

> a.set 0 100;;
FSI_0002.Mylib+Out_of_range: Exception of type 'FSI_0002.Mylib+Out_of_range' was thrown.
... 略 ...

> a.pop();;
FSI_0002.Mylib+Empty: Exception of type 'FSI_0002.Mylib+Empty' was thrown.
... 略 ...

どうやら正常に動作しているようです。興味のある方はいろいろ試してみてください。

F# Programming