多相クラスの続きです。前回はクラスに型パラメータを指定することで「多相クラス」を実現しました。今回は「抽象型」を使って多相的なクラスを作る方法を紹介します。それから、型境界と変位という型パラメータを制限する方法について説明します。
Scala の抽象クラスやトレイトでは、抽象メソッドや抽象フィールド変数を宣言することができますが、同じように「型」も type 文で抽象的に宣言することができます。
type は型に別名を付ける働きをします。1 の方法は既存の型に新しい名前を付けます。2 のように = 以降を省略すると、その名前は抽象型になります。抽象クラスやトレイトでは、type で抽象型を宣言し、その型を使ってフィールド変数やメソッドを定義します。そして、抽象型を宣言しているクラスやトレイトを継承 (または Mix-in) して具象クラスを作るとき、そのクラスで type で宣言した型名に具体的な型を指定します。
簡単な例題として、抽象型を使ってリストと配列でスタックを作ってみましょう。最初に、スタックの仕様を定義します。次のリストを見てください。
リスト : スタックの仕様
trait Stack {
type Item
def push(x: Item): Unit
def pop(): Item
def isEmpty(): Boolean
def isFull(): Boolean
def length(): Int
}
Stack はトレイトで定義しましたが、抽象クラスで定義してもかまいません。要素の型を type で Item と定義します。メソッド push は Item 型のデータ x を受け取って、それをスタックに格納します。pop はスタックから Item 型の要素を取り出します。あとのメソッドも簡単ですね。
次はリストを使って Stack の仕様を実装します。
リスト : リストを使った Stack の実装
trait ListStack extends Stack {
private var top: List[Item] = Nil
def push(x: Item): Unit = top = x :: top
def pop(): Item = {
if (top == Nil) throw new Exception("ListStack.pop: Stack is Empty")
val x = top.head
top = top.tail
x
}
def isEmpty(): Boolean = top == Nil
def isFull(): Boolean = false
def length(): Int = top.length
}
名前は ListStack としました。この段階では Item の型を決定できないので、Stack で定義されている型 Item を使ってメソッドを実装します。スタック本体のリストはフィールド変数 top に格納します。値を書き換える必要があるので var で宣言します。Nil はリストの要素がどんな型であっても空リストを表すので、Item の型が決まっていなくても変数 top に代入することができます。
メソッド push はコンス演算子で引数 x を top の先頭に追加して、top を新しい値に書き換えます。pop は最初にデータの有無をチェックして、データがなければエラーを送出します。そうでなければ、先頭の要素を取り出して変数 x にセットし、top の値を top.tail に書き換えます。最後に x を返します。あとのメソッドは簡単ですね。
最後に、Int を格納するスタックを作ります。次のリストを見てください。
リスト : Int を格納するスタック
class IntListStack extends ListStack {
type Item = Int
}
名前は IntListStack としました。extends で ListStack を継承し、type で Item に Int を設定するだけです。これで new IntListStack とすると、Int を格納するスタックを生成することができます。
それでは実行してみましょう。
scala> val a = new IntListStack val a: IntListStack = IntListStack@706ddbc8 scala> for (i <- 1 to 10) a.push(i) scala> a.length() val res1: Int = 10 scala> while (!a.isEmpty()) println(a.pop()) 10 9 8 7 6 5 4 3 2 1 scala> a.isEmpty() val res3: Boolean = true
また、次のように型パラメータを使ったスタックを作ることもできます。
リスト : 多相型のスタック
class PolyListStack[A] extends ListStack {
type Item = A
}
type で Item に型パラメータ A をセットすると、PolyListStack は型パラメータを使った多相クラスになります。
簡単な実行例を示します。
scala> val b = new PolyListStack[String]
val b: PolyListStack[String] = PolyListStack@27a6384b
scala> b.push("foo")
scala> b.push("bar")
scala> b.push("baz")
scala> while (!b.isEmpty()) println(b.pop())
baz
bar
foo
次は配列を使ってスタックを実装しましょう。配列でスタックを実現する場合、データを格納するための配列本体と、スタックのトップを表す変数が必要になります。本稿では、この変数を「スタックポインタ (stack pointer)」と呼ぶことにしましょう。次の図を見てください。
buffer 0 1 2 3 4 5 top
(1) [ ] 0 空の状態
(2) [ A ] 1 PUSH A
(3) [ A B ] 2 PUSH B
(4) [ A B C ] 3 PUSH C
(5) [ A B ] 2 POP => C
(6) [ A ] 1 POP => B
(7) [ ] 0 POP => A
図 : ベクタによるスタックの実現
まず、配列 buffer とスタックポインタ top を用意します。top の値は 0 に初期化しておきます。データをプッシュするときは buffer(top) にデータを格納してから、top の値をインクリメントします。逆にポップするときは、top の値をデクリメントしてから、buffer(top) にあるデータを取り出します。スタックを操作するたびに、top の値は上図のように変化します。
データをプッシュしていくと、top の値は配列の大きさと等しくなります。配列はリストと違って大きさに限りがあるので、これ以上データを追加することはできません。つまり、スタックは満杯となります。したがって、データをプッシュするとき、スタックに空きがあるかチェックする必要があります。また、top が 0 のときはスタックが空の状態なので、ポップすることはできません。このチェックも必要になります。
プログラムは次のようになります。
リスト : 配列を使ったスタックの実装
trait ArrayStack extends Stack {
protected val buff: Array[Item]
private var cnt: Int = 0
def push(x: Item): Unit = {
if (isFull()) throw new Exception("ArrayStack.push: Stack is Full")
buff(cnt) = x
cnt += 1
}
def pop(): Item = {
if (isEmpty()) throw new Exception("ArrayStack.pop: Stack is Empty")
cnt -= 1
buff(cnt)
}
def isEmpty(): Boolean = cnt == 0
def isFull(): Boolean = buff.size == cnt
def length(): Int = cnt
}
変数 buff はスタック本体を表す配列を格納します。型が決まらないと配列は生成できないので、ここでは抽象フィールド変数として定義します。cnt はスタックに格納されている要素の個数を表します。これをスタックポインタとして使います。
メソッド push は、最初にスタックに空きがあるかチェックします。満杯であればエラーを送出します。そうでなければ、buff(cnt) に x をセットして cnt を +1 します。pop は最初にスタックが空かチェックします。データがなければエラーを送出します。そうでなければ cnt を -1 してから buff(cnt) を返します。あとのメソッドは簡単ですね。
最後に、Int を格納するスタックを作ります。次のリストを見てください。
リスト : Int を格納するスタック
class IntArrayStack(size: Int) extends ArrayStack {
type Item = Int
protected val buff = new Array[Item](size)
}
名前は IntArrayStack としました。コンストラクタ引数 size でスタックの大きさを指定します。extends で ArrayStack を継承し、type で Item に Int を設定します。そして、new Array[Item](size) で配列本体を生成します。これで new IntArrayStack(10) とすると、Int を格納する大きさ 10 のスタックを生成することができます。
それでは実行してみましょう。
scala> val b = new IntArrayStack(10) val b: IntArrayStack = IntArrayStack@721e5f57 scala> for (i <- 1 to 10) b.push(i) scala> b.isFull() val res14: Boolean = true scala> while (!b.isEmpty()) println(b.pop()) 10 9 8 7 6 5 4 3 2 1 scala> b.isEmpty() val res16: Boolean = true
なお、ArrayStack は ListStack と違って、型パラメータを使った多相的なクラスを作ることはできません。
リスト : 型パラメータを使った多相クラス (コンパイルエラー)
class PolyArrayStack[A](size: Int) extends ArrayStack {
type Item = A
protected val buff = new Array[Item](size)
}
型 Item が決まらないので、配列を生成できずにコンパイルエラーとなります。型パラメータを使いたい場合は、要素の型を Any (または他のスーパークラス) に設定して配列を生成し、型変換を使ってデータの出し入れを行うことになります。実際、Scala のライブラリ scala.collection.mutable にあるクラス ArrayStack は型パラメータを使った多相クラスとして定義されています。
0 1 2 3 4 5 6 7 8 9
rear = 0 ↓
QUEUE [ ] : QUEUE は空
front= 0 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : データの追加
front= 0 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : 10を取り出す
front= 1 ↑
rear = 3 ↓
QUEUE [10 20 30 ] : 20,30を取り出す
front= 3 ↑
図 : キューの動作
前回は mutable なリストを使ってキュー (queue) を実現しました。キューは配列を使っても簡単に実現できます。先頭位置を示す front と末尾を示す rear を用意し、front と rear の間にあるデータをキューに格納されているデータとするのがポイントです。上の図を見てください。
まずキューは空の状態で、rear, front ともに 0 です。データの追加は、rear が示す位置にデータを書き込み、rear の値を +1 します。データ 10, 20, 30 を追加すると、図のようにデータが追加され rear は 3 になります。このとき front は 0 のままなので、先頭のデータは 10 ということになります。
次に、データを取り出す場合、front の示すデータを取り出してから front の値を +1 します。この場合、front が 0 なので 10 を取り出して front の値は 1 となり、次のデータ 20 が先頭になります。データを順番に 20, 30 と取り出していくと、3 つしかデータを書き込んでいないので当然キューは空になります。このとき front は 3 になり rear と同じ値になります。このように、front と rear の値が 0 の場合だけが空の状態ではなく、front と rear の値が等しくなると、キューは空になることに注意してください。
rear, fornt ともに値は増加していく方向なので、いつかは配列の範囲をオーバーします。このため、配列を先頭と末尾がつがっているリング状と考え、rear, front が配列の範囲を超えたら 0 に戻すことにします。これを「循環配列」とか「リングバッファ」と呼びます。一般に、配列を使ってキューを実装する場合は、リングバッファとするのが普通です。
最初に、キューの仕様を定義します。次のリストを見てください。
リスト : キューの仕様
trait Queue {
type Item
def enqueue(x: Item): Unit
def dequeue(): Item
def peek(): Item
def isEmpty(): Boolean
def isFull(): Boolean
def length(): Int
def clear(): Unit
}
トレイト Queue で抽象型 Item を定義します。あとのメソッドは前回作成したメソッドとほぼ同じです。
配列を使ったキューの実装は次のようになります。
リスト : 配列によるキューの実装
trait ArrayQueue extends Queue {
protected val buff: Array[Item]
protected var front = 0
protected var rear = 0
protected var cnt = 0
def enqueue(x: Item): Unit = {
if (isFull()) throw new Exception("ArrayQueue.enqueue Queue is Full")
buff(rear) = x
rear += 1
cnt += 1
if (buff.size == rear) rear = 0
}
def dequeue(): Item = {
if (isEmpty()) throw new Exception("ArrayQueue.dequeue Queue is Empty")
val x = buff(front)
front += 1
cnt -= 1
if (buff.size == front) front = 0
x
}
def peek(): Item = {
if (isEmpty()) throw new Exception("ArrayQueue.peek Queue is Empty")
buff(front)
}
def isEmpty(): Boolean = cnt == 0
def isFull(): Boolean = cnt == buff.size
def length(): Int = cnt
def clear() = {
front = 0
rear = 0
cnt = 0
}
}
変数 buff はスタック本体を表す配列を格納します。cnt はキューに格納されている要素の個数を表します。この変数を用意することで、キューの状態を簡単にチェックすることができます。
メソッド enqueue は、最初にキューに空きがあるかチェックします。満杯であればエラーを送出します。そうでなければ、buff(rear) に x をセットして rear と cnt を +1 します。そして、rear の値が配列の範囲を超えたならば 0 に戻します。
メソッド dequeue は、キューにデータがあるかチェックしてから、front の位置にあるデータを取り出して変数 x にセットします。あとは、cnt と front の値を +1 して、front の値が配列の範囲を超えたら 0 に戻します。
あとのメソッドは簡単なので説明は省略します。リストをお読みくださいませ。
最後に Int を格納するキュー IntArrayQueue を作ります。
リスト : Int を格納するキュー
class IntArrayQueue(size: Int) extends ArrayQueue {
type Item = Int
protected val buff = new Array[Item](size)
}
抽象型 Item を Int に設定し、buff に大きさ size の配列 Array[Int] をセットします。これでプログラムは完成です。
それでは、簡単な使用例を示しましょう。
scala> val a = new IntArrayQueue(10) val a: IntArrayQueue = IntArrayQueue@6eb089e6 scala> for (i <- 1 to 10) a.enqueue(i) scala> a.isFull() val res1: Boolean = true scala> a.length() val res2: Int = 10 scala> while (!a.isEmpty()) println(a.dequeue()) 1 2 3 4 5 6 7 8 9 10 scala> a.isEmpty() val res4: Boolean = true()
正常に動作していますね。
今まで作成したスタックは mutable なものですが、関数型言語では immutable なスタックが用いられます。imutable なスタックはリストを使って簡単に実現することができます。データを追加するときはリストの先頭に追加し、データを取り出すときはリストの先頭から行うように操作を限定すると、それはスタックの動作と同じになります。
プログラムは次のようになります。
リスト : immutable なスタック
case class imStack[A](top: List[A] = Nil) {
def push(x: A): imStack[A] = imStack[A](x :: top)
def pop: (A, imStack[A]) = top match {
case Nil => throw new Exception("imStack.pop: Stack is Empty")
case x::xs => (x, imStack[A](xs))
}
def isEmpty: Boolean = top == Nil
def isFull: Boolean = false
def length: Int = top.length
}
case クラスで imStack を定義します。フィールド変数 top はリストを格納しますが、immutable であることに注意してください。したがって、push や pop でスタックを操作する場合、新しい imStack を生成して返すことになります。push はデータをリストの先頭に追加した imStack を返します。pop はリストの先頭要素を取り除き、その要素と新しい imStack をタプルに格納して返します。スタックが空の場合はエラーを送出します。
簡単な使用例を示します。
scala> val a = new imStack[Int] val a: imStack[Int] = imStack(List()) scala> a.isEmpty val res0: Boolean = true scala> val b = a.push(1) val b: imStack[Int] = imStack(List(1)) scala> val c = b.push(2) val c: imStack[Int] = imStack(List(2, 1)) |
scala> val d = c.push(3) val d: imStack[Int] = imStack(List(3, 2, 1)) scala> val (x, e) = d.pop val x: Int = 3 val e: imStack[Int] = imStack(List(2, 1)) scala> val (y, f) = e.pop val y: Int = 2 val f: imStack[Int] = imStack(List(1)) scala> val (z, g) = f.pop val z: Int = 1 val g: imStack[Int] = imStack(List()) |
正常に動作していますね。関数型言語の場合、変数の値を書き換えることができないので、push や pop の返り値を別の変数に格納する必要があります。面倒なように思えますが、immutable なデータ構造は再帰定義や高階関数といっしょに使うと便利です。たとえば、リストの要素をスタックに格納する場合は次のようになります。
scala> List(1,2,3,4,5,6,7,8).foldLeft(new imStack[Int])(_.push(_)) val res1: imStack[Int] = imStack(List(8, 7, 6, 5, 4, 3, 2, 1))
プレイスホルダーを使って、(a, x) => a.push(x) を _.push(_) で表していることに注意してください。
今度はリストを使って immutable なキューを作ってみましょう。リストを使ってキューを実装する場合、キューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。
ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。たとえば、データの追加に演算子 ::: を使うと、データを追加するたびにリスト（キュー）がコピーされてしまいます。このため、キューに格納されているデータが多くなると時間がかかるようになります。
これを回避する方法はいろいろ考えられるのですが、今回は関数型言語 (SML/NJ など) でよく使われている方法を紹介します。次の図を見てください。
先頭
変数 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
front ─→│０│・┼─→│１│・┼─→│２│／│
└─┴─┘ └─┴─┘ └─┴─┘
最後尾
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
rear ─→│５│・┼─→│４│・┼─→│３│／│
└─┴─┘ └─┴─┘ └─┴─┘
図 : キューの構造
上図は 2 つのリストでキューを表しています。データを取り出すときは front のリストを、データを追加するときは rear のリストを使います。front と rear で一つのキューを構成し、rear のリストはデータを逆順で格納することになります。ようするに、front が先頭で rear が最後尾になるわけです。上図のキューを一つのリストで表すと (0, 1, 2, 3, 4, 5) になります。
したがって、front が空リストでも rear にデータがあれば、キューは空ではありません。rear のリストを逆順にして front にセットし、rear を空リストにします。これで front からデータを取り出すことができます。キューが空の状態は front と rear が両方とも空リストの場合です。
それではプログラムを作りましょう。次のリストを見てください。
リスト : immutable なキューの実装
case class imQueue[A](front: List[A] = Nil, rear: List[A] = Nil) {
def enqueue(x: A): imQueue[A] = imQueue[A](front, x::rear)
def dequeue: (A, imQueue[A]) = {
if (isEmpty) throw new Exception("imQueue.dequeue: Queue is Empty")
front match {
case Nil => imQueue[A](rear.reverse, Nil).dequeue
case x::xs => (x, imQueue[A](xs, rear))
}
}
def peek: A = {
if (isEmpty) throw new Exception("imQueue.peek: Queue is Empty")
front match {
case Nil => rear.reverse.head
case x::_ => x
}
}
def isEmpty: Boolean = front == Nil && rear == Nil
def length: Int = front.length + rear.length
}
case クラスで imQueue を定義します。フィールド変数は front と rear の 2 つです。どちらも immutable であることに注意してください。
equeue はキューにデータ x を追加します。これは x を rear の先頭に追加するだけです。dequeue はキューからデータを取り除きます。キューが空の場合はエラーを送出します。front が空リストの場合は、キュー imQueue(rear.reverse, Nil) を作って dequeue を再帰呼び出しします。front にデータがある場合はパターン x::xs とマッチングさせ、x と imQueue(xs, rear) をタプルに格納して返します。peek はキューの先頭要素を返します。処理は dequeue とほとんど同じで、違いはキューの先頭要素を返すだけです。あとのメソッドは簡単ですね。
それでは簡単な実行例を示します。
scala> val a = List(1,2,3,4,5,6,7,8).foldLeft(new imQueue[Int])(_.enqueue(_)) val a: imQueue[Int] = imQueue(List(),List(8, 7, 6, 5, 4, 3, 2, 1)) scala> val (x, b) = a.dequeue val x: Int = 1 val b: imQueue[Int] = imQueue(List(2, 3, 4, 5, 6, 7, 8),List()) scala> val (y, c) = b.dequeue val y: Int = 2 val c: imQueue[Int] = imQueue(List(3, 4, 5, 6, 7, 8),List()) scala> val (z, d) = c.dequeue val z: Int = 3 val d: imQueue[Int] = imQueue(List(4, 5, 6, 7, 8),List()) scala> d.peek val res2: Int = 4
正常に動作していますね。
Scala の型パラメータは任意の型を表しますが、プログラムによっては型に制限をかけたい場合があります。Scala は型パラメータの指定で「上限境界」と「下限境界」という制限を設定することができます。
1. 上限境界 A <: Foo, 型 A は型 Foo か、そのサブクラス 2. 下限境界 A >: Baz, 型 A は型 Baz か、そのスーパークラス
これを「型境界」といいます。型境界は type の抽象型でも設定することができます。
簡単な例を示しましょう。
scala> class Foo // defined class Fooclass Foo scala> class Bar extends Foo // defined class Bar scala> class Baz extends Bar // defined class Baz scala> class Oops[A <: Bar] // defined class Oops scala> new Oops[Foo] -- [E057] Type Mismatch Error: -------------------------------------- 1 |new Oops[Foo] | ^ | Type argument Foo does not conform to upper bound Bar | | longer explanation available when compiling with `-explain` -- [E057] Type Mismatch Error: -------------------------------------- 1 |new Oops[Foo] | ^ | Type argument Foo does not conform to upper bound Bar | | longer explanation available when compiling with `-explain` 2 errors found scala> new Oops[Bar] val res1: Oops[Bar] = Oops@d70e9a scala> new Oops[Baz] val res2: Oops[Baz] = Oops@13a268cd
継承関係が Foo - Bar - Baz というクラスを作ります。クラス Oops は多相クラスで、型パラメータに A <: Bar を指定しているので、指定できる型は Bar または Bar のサブクラスである Baz になります。new Oops[Foo] とするとエラーになりますが、Oops[Bar] と Oops[Baz] はインスタンスを生成できます。
scala> class Oops1[A >: Bar] // defined class Oops1 scala> new Oops1[Foo] val res3: Oops1[Foo] = Oops1@14ad42 scala> new Oops1[Bar] val res4: Oops1[Bar] = Oops1@3a917017 scala> new Oops1[Baz] -- [E057] Type Mismatch Error: --------------------------------------- 1 |new Oops1[Baz] | ^ | Type argument Baz does not conform to lower bound Bar | | longer explanation available when compiling with `-explain` -- [E057] Type Mismatch Error: --------------------------------------- 1 |new Oops1[Baz] | ^ | Type argument Baz does not conform to lower bound Bar | | longer explanation available when compiling with `-explain` 2 errors found
クラス Oops1 の型パラメータは A >: Bar なので、今度は Bar または Bar のスーパークラス Foo でインスタンスを生成できます。Bar のサブクラス Baz を指定して new Oops1[Baz] とするとエラーになります。
また、上限境界と下限境界を同時に設定することもできます。
[A >: Baz <: Bar]
これで Baz 以上 Bar 以下のクラス、つまり、Bar と Baz に型パラメータ A を限定することができます。
それでは簡単な例題として、リストを挿入ソートする関数 insertSort を多相型関数に改良してみましょう。次のように、単純に型パラメータを指定するだけではコンパイルでエラーになります。
リスト : 単純挿入ソート (コンパイルエラー)
def insertSort[A](xs: List[A]): List[A] = {
def insertElement(x: A, xs: List[A]): List[A] =
xs match {
case Nil => List(x)
case y::ys => if (x < y) x::y::ys else y::insertElement(x, ys)
}
xs match {
case Nil => Nil
case y::ys => insertElement(y, insertSort(ys))
}
}
型パラメータ A だけでは、リストの要素の型に演算子 < が定義されているか判定できないので、コンパイルエラーになります。この場合、トレイト Ordered[A] を継承して、型パラメータに上限境界を指定します。Ordered は次のように比較演算子を定義しています。
リスト : Ordered (Ordered.scala より抜粋)
trait Ordered[A] extends Any with java.lang.Comparable[A] {
/*
* Returns `x` where:
* - `x < 0` when `this < that`
* - `x == 0` when `this == that`
* - `x > 0` when `this > that`
*/
def compare(that: A): Int
def < (that: A): Boolean = (this compare that) < 0
def > (that: A): Boolean = (this compare that) > 0
def <= (that: A): Boolean = (this compare that) <= 0
def >= (that: A): Boolean = (this compare that) >= 0
def compareTo(that: A): Int = compare(that)
}
Scala の場合、比較演算子もメソッドです。Orderd を継承して抽象メソッド compare をオーバーライドすれば比較演算子を使用することができます。
簡単な例として、点を表す Point クラスで Orderd を継承してみましょう。次のリストを見てください。
リスト : Point クラス
case class Point(val x: Double, val y: Double) extends Ordered[Point] {
def distance(that: Point): Double = {
val dx = x - that.x
val dy = y - that.y
Math.sqrt(dx * dx + dy * dy)
}
def compare(that: Point): Int = {
val a = Math.sqrt(x * x + y * y)
val b = Math.sqrt(that.x * that.x + that.y * that.y)
if (a == b) 0 else if (a < b) -1 else 1
}
}
Ordered を継承するとき、型パラメータには Point を指定します。大小関係は、とりあえず原点 Point(0, 0) からの距離を基準にしましょう。あとは、compare で原点からの距離を求めて変数 a, b にセットし、a == b ならば 0 を、a < b ならば -1 を、a > b ならば 1 を返します。
簡単な実行例を示します。
scala> val a = Point(1, 1) val a: Point = Point(1.0,1.0) scala> val b = Point(2, 2) val b: Point = Point(2.0,2.0) scala> a < b val res6: Boolean = true scala> b > a val res7: Boolean = true scala> a >= a val res8: Boolean = true
あとは insertSort の型パラメータで、A <: Ordered[A] を指定すると、Point を格納したリストをソートすることができます。プログラムは次のようになります。
リスト : Point のソート
object sample1301 {
def insertSort[A <: Ordered[A]](xs: List[A]): List[A] = {
def insertElement(x: A, xs: List[A]): List[A] =
xs match {
case Nil => List(x)
case y::ys => if (x < y) x::y::ys else y::insertElement(x, ys)
}
xs match {
case Nil => Nil
case y::ys => insertElement(y, insertSort(ys))
}
}
def main(args: Array[String]): Unit = {
println(insertSort(List(Point(5,5), Point(4,4), Point(3,3), Point(2,2), Point(1,1))))
}
}
$ scala sample1301.scala $ scala sample1301 List(Point(1.0,1.0), Point(2.0,2.0), Point(3.0,3.0), Point(4.0,4.0), Point(5.0,5.0))
ただし、このままでは整数 (Int) を格納したリスト (List[Int]) をソートすることはできません。Int だけではなく、Double など基本的な数は Ordered を継承 (または Mix-in) していないからです。この場合、implicit parameter という機能を使うと、Int や Double でもソートすることができます。implicit parameter については回を改めて説明する予定です。
Scala の型パラメータは境界の指定だけではなく、「変位」を指定することができます。たとえば、Foo - Bar - Baz という継承関係を持つクラスと多相クラス Oops[A] があるとします。型 Oops[Foo] と Oops[Bar] に直接の関係はありませんが、型パラメータに指定するクラスの継承関係を使って、多相クラスでも親子関係 (スーパークラスとサブクラスの関係) を考えることができます。Scala では、この機能を「変位」といいます。
変位の指定には「非変 (nonvariant)」、「共変 (covariant)」、「反変 (contravariant)」の 3 通りあります。今までのように型パラメータ A だけ指定すると「非変」になります。これは多相クラスに親子関係を持たせない方法です。次の例を見てください。
scala> class Foo // defined class Foo scala> class Bar extends Foo // defined class Bar scala> class Baz extends Bar // defined class Baz scala> class Oops[A] // defined class Oops scala> var a: Oops[Foo] = new Oops[Foo] var a: Oops[Foo] = Oops@2b9aeedb scala> a = new Oops[Bar] -- [E007] Type Mismatch Error: -------------------------------- 1 |a = new Oops[Bar] | ^^^^^^^^^^^^^ | Found: Oops[Bar] | Required: Oops[Foo] | | longer explanation available when compiling with `-explain` 1 error found scala> a = new Oops[Baz] -- [E007] Type Mismatch Error: --------------------------------- 1 |a = new Oops[Baz] | ^^^^^^^^^^^^^ | Found: Oops[Baz] | Required: Oops[Foo] | | longer explanation available when compiling with `-explain` 1 error found
多相クラスに親子関係があるならば、親クラスの変数に子クラスのインスタンスを代入することができます。非変の場合、多相クラスに親子関係はないので、上記のように Oops[Foo] と宣言した変数 a に代入できるのは Oops[Foo] だけで、Oops[Bar] や Oops[Baz] のインスタンスは代入できません。
共変は型パラメータで指定するクラスと同じ親子関係を設定する方法です。したがって、型パラメータ A で指定したクラスのサブクラスも同じ変数に代入することができます。共変の指定は型パラメータの前に + を付けます。次の例を見てください。
scala>class Oops1[+A] // defined class Oops1 scala> var a: Oops1[Foo] = new Oops1[Foo] var a: Oops1[Foo] = Oops1@3a5244a1 scala> a = new Oops1[Bar] a: Oops1[Foo] = Oops1@5aef36a9 scala> a = new Oops1[Baz] a: Oops1[Foo] = Oops1@7e3b101b scala> var b: Oops1[Bar] = new Oops1[Foo] -- [E007] Type Mismatch Error: -------------------------------- 1 |var b: Oops1[Bar] = new Oops1[Foo] | ^^^^^^^^^^^^^^ | Found: Oops1[Foo] | Required: Oops1[Bar] | | longer explanation available when compiling with `-explain` 1 error found
クラス Oops1 は型パラメータで +A と指定しているので共変になります。変数 a を Oops1[Foo] と宣言すると、Foo[Bar] や Foo[Baz] のインスタンスでも代入することができます。変数 b は Oops1[Bar] と宣言しているので、Oosp1[Foo] のインスタンスは代入できません。
共変とは逆に、反変は指定したクラスと逆の親子関係を設定する方法です。Foo のサブクラスが Bar とすると、反変は Oops[Bar] が Oops[Foo] のスーパークラスになります。反変は型パラメータの前に - を付けます。次の例を見てください。
scala> class Oops2[-A] // defined class Oops2 scala> var a: Oops2[Bar] = new Oops2[Bar] var a: Oops2[Bar] = Oops2@48e0e779 scala> a = new Oops2[Foo] a: Oops2[Bar] = Oops2@1215982f scala> a = new Oops2[Baz] -- [E007] Type Mismatch Error: -------------------------------- 1 |a = new Oops2[Baz] | ^^^^^^^^^^^^^^ | Found: Oops2[Baz] | Required: Oops2[Bar] | | longer explanation available when compiling with `-explain` 1 error found
クラス Oops2 の型パラメータは -A なので反変になります。変数 a は Oops2[Bar] と宣言されているので、Oops2[Bar] だけではなく Oops2[Foo] のインスタンスも格納することができます。ただし、Oops2[Baz] のインスタンスは格納することができません。
Scala の場合、mutable な多相型データ構造は非変に設定します。次の例を見てください。
scala> class Foo[A](var x: A) // defined class Foo scala> val a = new Foo[Int](10) val a: Foo[Int] = Foo@61f26cba scala> a.x val res0: Int = 10 scala> a.x = 20 scala> a.x val res1: Int = 20
もしも、型パラメータ A を共変に設定すると、次のプログラムが動作することになります。
val a = new Foo[Int](10) val b: Foo[Any] = a a.x = "oops" => エラー
型 Any はすべてのオブジェクトのスーパークラスです。変数 b の型を Foo[Any] と宣言すれば、Int は Any のサブクラスなので、変数 a のインスタンスを変数 b に代入することができます。変数 b の型は Foo[Any] なので、ここに文字列を代入してもいいはずですが、b の実体は Foo[Int] で Int しか格納することができません。この場合、実行時にエラーを送出することになるでしょう。
実際、Scala の配列は非変に設定されていますが、Java の配列は共変です。Java の場合、配列を使って上記のようなプログラムを書くことが可能です。次のリストを見てください。
リスト : Java の配列は共変 (test.java)
public class test {
public static void main(String[] args){
Integer [] a = new Integer [] {1, 2, 3, 4};
Object [] b = a;
b[0] = 10;
for (Object x: b) System.out.println(x);
}
}
$ javac test.java $ java test 10 2 3 4
Integer の配列 a を作成します。変数 b を Object の配列に宣言すると、変数 b に a の配列を代入することができます。配列の値を Integer 以外の値に書き換えなければ、このプログラムでも正常に動作します。
ところが、配列 b は Object で宣言しているので、そこに文字列を代入することができます。次のリストを見てください。
リスト : Java の配列は共変 (実行時エラー)
public class test {
public static void main(String[] args){
Integer [] a = new Integer [] {1, 2, 3, 4};
Object [] b = a;
b[0] = "hello, world";
for (Object x: b) System.out.println(x);
}
}
b[0] に文字列をセットします。実際、コンパイルしてもエラーにはならないのですが、実行すると例外が送出されます。
$ javac test.java
$ java test
Exception in thread "main" java.lang.ArrayStoreException: java.lang.String
at test.main(test.java:5)
Scala では、配列を非変に設定しているので、このような危険なプログラムを書くことはできません。
それでは、型パラメータ A に反変を設定することはできるのでしょうか。実際に試してみると、次のようなエラーが出ます。
scala> class Foo[-A](var x: A)
-- Error: -------------------------------------------------------------------
1 |class Foo[-A](var x: A)
| ^^^^^^^^
| contravariant type A occurs in covariant position in type A
of variable x
1 error found
参考 URL によると、Scala のメソッドは、仮引数の変位を反変に、返り値の変位を共変に設定しているようです。メソッド x はフィールド変数 x の値を返すので返り値の型は A で変位は反変になります。共変の位置に反変の型パラメータ A が出現している場合、Scala はコンパイルエラーとするようです。逆に、反変の位置に共変の型パラメータが出現してもコンパイルエラーになります。
もしも、型パラメータ A に反変を許したらどうなるのでしょう。次の例を見てください。
scala> class Foo { def foo() = println("Foo") }
// defined class Foo
scala> class Bar extends Foo { def bar() = println("Bar") }
// defined class Bar
class Baz[-A](var x: A) val a: Baz[Foo] = new Baz(new Foo) val b: Baz[Bar] = a a.x.bar() => エラー
Bar は Foo のサブクラスなので、Baz[Foo] は Baz[Bar] のサブクラスになります。したがって、Baz[Foo] のインスタンス a は、スーパークラス Baz[Bar] の変数 b にセットすることができます。変数 b は Baz[Bar] なので、a.x の型は Bar でメソッド bar を呼び出すことができるはずです。ですが、b の実体は Baz[Foo] であり、Foo にメソッド bar はありません。この場合も実行時にエラーが送出されることになるでしょう。
型パラメータの変位を共変に設定すると、次のように動作します。ただし、フィールド変数 x を immutable にします。
scala> class Baz[+A](val x: A) // defined class Baz scala> val a = new Baz[Bar](new Bar) val a: Baz[Bar] = Baz@f11fe28 scala> val b: Baz[Foo] = a val b: Baz[Foo] = Baz@f11fe28 scala> b.x.foo() Foo
変位は共変なので、Baz[Foo] は Baz[Bar] のスーパークラスになり、Baz[Bar] のインスタンス a を、Bar[Foo] で宣言した変数 b に代入することができます。そして、b.x.foo() でメソッド foo を呼び出すことができます。これは Bar が Foo のメソッド foo を継承しているので、問題なく動作します。Scala の場合、immutable な多相クラスは変位を共変に設定するようです。
今回はここまでです。次回は多相クラスを使って実際に immutable なデータ構造を作ってみましょう。