多相クラスの続きです。今回は多相クラスで immutable なデータ構造を作ってみましょう。具体的には、「連結リスト」と「二分探索木」で作成したプログラムを多相的なデータ構造に改良します。
Scala 初心者 (M.Hiroi も含む) にとって、型境界や変位は複雑で難しい機能なのですが、Scala のライブラリではよく使われています。まず最初に、簡単な例として Option を取り上げてみましょう。クラス名を MyOption, MySome, MyNone に変更して、実際にプログラムを作ってみます。
MyOption は多相型の抽象クラスで表すことにすると、MySome は多相型の case クラスで MyOption を継承すればいいでしょう。次に MyNone の定義ですが、シングルトンオブジェクは多相型にはならない (型パラメータの指定はできない) ので、MyOption を継承するときの型パラメータの指定が問題になります。このような場合、Nothing という型を使います。
Scala の型 Any はすべてのクラスのスーパークラスですが、同じように Scala にはすべてのクラスのサブクラスを表す型があり、それを Nothing といいます。Nothing に値 (インスタンス) はありません。値が無いことを表すためにも Nothing は使われます。次の例を見てください。
scala> class Foo[+A] // defined class Foo scala> var a: Foo[Int] = new Foo[Int] var a: Foo[Int] = Foo@cedee22 scala> a = new Foo[Nothing] a: Foo[Int] = Foo@72f3acc9 scala> var b: Foo[Double] = new Foo[Double] var b: Foo[Double] = Foo@5dbab232 scala> b = new Foo[Nothing] b: Foo[Double] = Foo@6c75e3bc scala> var c: Foo[String] = new Foo[String] var c: Foo[String] = Foo@2d4f67e scala> c = new Foo[Nothing] c: Foo[String] = Foo@1c135f63
多相クラス Foo[+A] を定義します。型パラメータを共変に指定すると、Foo[Nothing] は Foo[Int], Foo[Double], Foo[String] など、型パラメータがどんな型であっても、その変数に代入することができます。したがって、MyOption を共変で定義すると、MyOption[Nothing] は型パラメータがどんな型でも変数に代入することができます。
そして、MyNone が MyOption[Nothing] を継承すれば、MyNone のスーパークラス MyOption[Noting] を代入できる変数であれば、MyNone もそこに代入することができます。プログラムは次のようになります。
scala> abstract class MyOption[+A] {
| def get: A
| def isEmpty: Boolean
| }
|
| case class MySome[A](x: A) extends MyOption[A] {
| def get: A = x
| def isEmpty: Boolean = false
| }
|
| case object MyNone extends MyOption[Nothing] {
| def get = throw new Exception("MyNone.get")
| def isEmpty: Boolean = true
| }
// defined class MyOption
// defined case class MySome
// defined case object MyNone
MyOption は抽象クラスで型パラメータに +A を指定します。簡単な例題なので、メソッドは get と isEmpty だけにしました。MySome は case クラスで定義して、MyOption[A] を継承します。MyNone は object で定義し、MyOption[Nothing] を継承します。get はエラーを送出します。これで基本的な機能は Option と同じように動作します。
簡単な実行例を示します。
scala> val a: MyOption[Int] = MySome(10) val a: MyOption[Int] = MySome(10) scala> val b: MyOption[Int] = MyNone val b: MyOption[Int] = MyNone scala> val MySome(c) = a -- Warning: ------------------------------ ... 略 ... val c: Int = 10 scala> a.get val res0: Int = 10 scala> a.isEmpty val res1: Boolean = false scala> b.isEmpty val res2: Boolean = true scala> b.get java.lang.Exception: MyNone.get at rs$line$9$MyNone$.get(rs$line$9:12) at rs$line$9$MyNone$.get(rs$line$9:12) ... 33 elided
正常に動作していますね。
「immutable な連結リスト」は空リスト Nils をシングルトンオブジェクトで定義しました。ということは、MyOption と同じように連結リストも共変でなければいけません。多相型の連結リストを ImList, セルを Cons, 空リストを Nils とすると、クラスの定義は次のようになります。
リスト : 多相的な連結リスト (immutable)
package imlist
// 抽象クラス
abstract class ImList[+A] {
def isEmpty: Boolean
def car: A
def cdr: ImList[A]
//
// メソッドの定義 (省略)
//
}
// セル
case class Cons[A](item: A, next: ImList[A]) extends ImList[A] {
def isEmpty: Boolean = false
def car: A = item
def cdr: ImList[A] = next
}
// 空リスト
case object Nils extends ImList[Nothing] {
def isEmpty: Boolean = true
def car = throw new Exception("ImList.car: Empty list")
def cdr = throw new Exception("ImList.cdr: Empty list")
}
ImList は抽象クラスで、型パラメータ A の変位を共変に設定します。セルを表すクラス Cons も多相クラスとし、抽象クラス ImList[A] を継承します。フィールド変数 item の型は A で、next は ItemList[A] になります。
リストの終端を表すシングルトンオブジェクト Nils は ImList[Nothong] を継承します。実際の List はもっと多機能で複雑ですが、基本的な機能はこれだけで実現することができます。ちなみに、Scala の List も共変です。
簡単な実行例を示します。
scala> :load imlist.scala // defined class ImList // defined case class Cons // defined case object Nils scala> val a: ImList[Int] = Cons(1, Cons(2, Cons(3, Cons(4, Nils)))) val a: imlist.ImList[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Nils)))) scala> a.car val res0: Int = 1 scala> a.cdr val res1: ImList[Int] = Cons(2,Cons(3,Cons(4,Nils))) scala> a.isEmpty val res2: Boolean = false scala> a.cdr.cdr.cdr.cdr.isEmpty val res3: Boolean = true
immutable な連結リストは、次のように他のデータ型も挿入することができます。
scala> Cons(1.234, a)
val res4: Cons[Double | Int] = Cons(1.234,Cons(1,Cons(2,Cons(3,Cons(4,Nils)))))
scala> Cons("oops", a)
val res5: Cons[String | Int] = Cons(oops,Cons(1,Cons(2,Cons(3,Cons(4,Nils)))))
scala> val b :ImList[Int] = Cons("oops", a)
-- [E007] Type Mismatch Error: --------------------------------
1 |val b :ImList[Int] = Cons("oops", a)
| ^^^^^^
| Found: ("oops" : String)
| Required: Int
|
| longer explanation available when compiling with `-explain`
1 error found
このとき、新しいリストの型は元のリストの型とは異なることに注意してください。リスト a に実数 1.234 を追加すると、新しく生成されるリストの型は ImList[Double | Int] になります。Double | Int は、Int または Double を表す型で、Union Types といいます。これは Scala3 で導入された新しい機能です。リスト a に文字列 "oops" を追加すると、新しいリストの型は ImList[String | Int] になります。もちろん、リスト a の型が変わることはありません。
Scala は型推論で新しいリストの型を決定しますが、Int と Double を格納する場合、新しいリストは両者を格納できる Double | Int 型のリストとするしかありません。つまり、ImList[Int] を ImList[Double | Int] に変換しているわけです。
また、ImList[A] は共変なので、スーパークラスの変数にリストを代入することはできますが、サブクラスの変数に代入することはできません。ImList[Int] のリストに間違って文字列を挿入すると ImList[Double | Int] になりますが、Double | Int と Int に継承関係はないので、それを ImList[Int] の変数にセットしようとするとコンパイルエラーになります。
次はメソッドを作成します。基本的には要素の型 Int を型パラメータ A に、リストの型 imlist を ImList[A] に書き換えるだけですが、データを挿入するメソッド insert は注意が必要です。次のように書き換えるとエラーになります。
リスト : データの挿入 (コンパイルエラー)
def insert(n: Int, x: A): ImList[A] =
if (n == 0) Cons(x, this)
else if (isEmpty) throw new Exception("ImList.insert: out of range")
else Cons(car, cdr.insert(n - 1, x))
scala> :load imlist.scala
-- Error: -------------------------------------------------------------------
25 | def insert(n: Int, x: A): ImList[A] =
| ^^^^
| covariant type A occurs in contravariant position in
type A of parameter x
1 error found
引数 x の型に共変の型パラメータ A が使われているためエラーになります。この場合、A を新しい型パラメータに置き換えます。次のリストを見てください。
リスト : データの挿入 (修正版)
def insert[B >: A](n: Int, x: B): ImList[B] =
if (n == 0) Cons(x, this)
else if (isEmpty) throw new Exception("ImList.insert: out of range")
else Cons(car, cdr.insert(n - 1, x))
x の型をパラメータ B で表します。返り値の型は ImList[B] になります。このとき、型境界を指定します。挿入する要素の型によって、型 B は型 A のスーパークラスになることがありますね。つまり、下限境界 B >: A を設定すればいいわけです。これでコンパイルすることができます。
あとのプログラムの修正は簡単なので説明は割愛します。詳細はプログラムリスト１をお読みくださいませ。
それでは実際に試してみましょう。
scala> val a: ImList[Int] = Cons(1, Cons(2, Cons(3, Cons(4, Nils)))) val a: ImList[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Nils)))) scala> a(0) val res0: Int = 1 scala> a(3) val res1: Int = 4 scala> a.insert(0, 0) val res2: ImList[Int] = Cons(0,Cons(1,Cons(2,Cons(3,Cons(4,Nils))))) scala> a.insert(4, 0) val res3: ImList[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Cons(0,Nils))))) scala> a.insert(0, 1.234) val res4: ImList[Int | Double] = Cons(1.234,Cons(1,Cons(2,Cons(3,Cons(4,Nils))))) scala> a.insert(0, "oops") val res5: ImList[Int | String] = Cons(oops,Cons(1,Cons(2,Cons(3,Cons(4,Nils))))) scala> a.delete(0) val res6: ImList[Int] = Cons(2,Cons(3,Cons(4,Nils))) scala> a.delete(0).delete(2) val res7: ImList[Int] = Cons(2,Cons(3,Nils)) scala> a.delete(0).delete(2).delete(1) val res8: ImList[Int] = Cons(2,Nils) scala> a.delete(0).delete(2).delete(1).delete(0) val res9: ImList[Int] = Nils scala> a.delete(0).delete(2).delete(1).delete(0).isEmpty val res10: Boolean = true scala> a.map(x => x * x) val res11: ImList[Int] = Cons(1,Cons(4,Cons(9,Cons(16,Nils)))) scala> a.filter(_ % 2 == 0) val res12: ImList[Int] = Cons(2,Cons(4,Nils)) scala> a.foldl(0, (_ :Int) + (_:Int)) val res13: Int = 10 scala> a.foldr(0, (_ :Int) + (_:Int)) val res14: Int = 10 scala> a.foreach(println) 1 2 3 4
正常に動作していますね。
scala のメソッドには、引数が省略されたとき implicit で宣言した値を暗黙のうちに渡す機能があります。これを「暗黙のパラメータ (implicit parameter)」といいます。暗黙のパラメータは引数名の前に implicit を付けて宣言します。
def メソッド名(仮引数名: 型, ...) (implicit 暗黙引数名: 型): 返り値の型 = ...
implicit は引数リストの先頭にしか付けることができないので、引数をカッコで分けて記述することが多いと思います。暗黙のパラメータが省略されると、implicit で宣言された値の中で、型と一致するものがメソッドに渡されます。一致する値が無ければコンパイルエラーになります。
簡単な例を示しましょう。
scala> implicit val a: Int = 10
val a: Int = 10
scala> implicit val b: Double = 1.2345
val b: Double = 1.2345
scala> def foo(x: Int)(implicit y: Int): (Int, Int) = (x, y)
def foo(x: Int)(implicit y: Int): (Int, Int)
scala> def bar(x: Int)(implicit y: Double): (Int, Double) = (x, y)
def bar(x: Int)(implicit y: Double): (Int, Double)
scala> def baz(x: Int)(implicit y: String): (Int, String) = (x, y)
def baz(x: Int)(implicit y: String): (Int, String)
scala> foo(1)
val res0: (Int, Int) = (1,10)
scala> foo(1)(2)
val res1: (Int, Int) = (1,2)
scala> bar(1)
val res2: (Int, Double) = (1,1.2345)
scala> bar(1)(12.345)
val res3: (Int, Double) = (1,12.345)
scala> baz(1)
-- [E172] Type Error: -----------------------------------------------------------
1 |baz(1)
| ^
| No given instance of type String was found for parameter y of method baz
1 error found
scala> baz(1)("oops")
val res5: (Int, String) = (1,oops)
メソッド foo, bar, baz には暗黙のパラメータ y が定義されていて、その型はそれぞれ Int, Double, String です。Int と Double は変数 a と b に定義されています。a, b は implicit で宣言されているので、foo(1) とすると a の値 (10) が渡され、bar(1) とすると b の値 (1.2345) が渡されます。
String の値は implicit で宣言されていないので、bar(1) を呼び出すとエラーになります。もちろん、暗黙引数を省略しなければ、実引数が暗黙引数 y の値になります。
ところで、昔の Scala には「可視境界 (view bound)」という型境界の指定方法がありました。
A <% T
型 A は型 T のサブクラスか、もしくは「暗黙の型変換」で A から T に変換できることが条件になります。ところが、可視境界は Scala 2.13.5 で非推奨の機能になったので、かわりに暗黙のパラメータを使います。暗黙のパラメータに型変換を行う関数を指定すると、暗黙の型変換を行わせることができます。
簡単な例として、「高階関数 (2)」で作成したクイックソートを暗黙のパラメータを使って多相型関数に改良してみましょう。次のリストを見てください。
リスト : クイックソート (多相型)
import scala.math.Ordered.orderingToOrdered
object sample1501 {
def quickSort[A](xs: List[A])(implicit f: A => Ordered[A]): List[A] =
xs match {
case Nil => Nil
case p::ys => {
val a = for (y <- ys if y < p) yield y
val b = for (y <- ys if y >= p) yield y
quickSort(a) ::: List(p) ::: quickSort(b)
}
}
}
ソートするリストの要素を型パラメータ A で表します。Scala3 の場合、Int, Double, String など、基本的なデータは Ordered への変換関数が scala.math.Ordered.orderingToOrdered に用意されています。暗黙のパラメータ f の型に A => Ordered[A] を設定すればリストをソートすることができます。
簡単な実行例を示します。
scala> :load sample1501.scala
// defined object sample1501
scala> import sample1501._
scala> quickSort(List(5,6,4,7,3,8,2,9,1,0))
val res1: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
scala> quickSort(List(1.1, 2.2, 5.5, 4.4, 3.3))
val res2: List[Double] = List(1.1, 2.2, 3.3, 4.4, 5.5)
scala> quickSort(List("foo", "bar", "baz", "oops"))
val res3: List[String] = List(bar, baz, foo, oops)
次は、「immutable な二分木」を多相型に改良しましょう。空の木 imEmpty はシングルトンオブジェクトで定義しているので、二分木を表す多相クラスも共変でなければいけません。多相型の二分木を ImTree, 節を imNode, 空の木を imEmpty とすると、クラスの定義は次のようになります。
リスト : immutable な二分木 (多相型)
import scala.math.Ordered.orderingToOrdered
abstract class ImTree[+A] {
def isEmpty: Boolean
def item: A
def left: ImTree[A]
def right: ImTree[A]
//
// メソッドの定義 (省略)
//
}
case class imNode[A](item: A, left: ImTree[A], right: ImTree[A]) extends ImTree[A] {
def isEmpty: Boolean = false
}
case object imEmpty extends ImTree[Nothing] {
def isEmpty: Boolean = true
def item = throw new Exception("item: Empty Tree")
def left = throw new Exception("left: Empty Tree")
def right = throw new Exception("right: Empty Tree")
}
ImTree は抽象クラスで、型パラメータ A の変位を共変に設定します。節を表すクラス imNode も多相クラスとし、抽象クラス ImTree[A] を継承します。フィールド変数 item の型は A で、left と right は ImTree[A] になります。空の木を表すシングルトンオブジェクト imEmpty は ImTree[Nothong] を継承します。要素の型 A は Ordered に変換できるものとします。設定はメソッドで行います。
次はメソッドを作成します。基本的には要素の型 Int を型パラメータ A に、二分木の型 imTree を ImTree[A] に書き換えるだけですが、データを比較するため暗黙のパラメータを設定することと、共変のパラメータ A が引数に出現する場合があるので、パラメータの書き換えが必要になります。
メソッド search, insert, delete は次のようになります。
リスト : 二分木の基本メソッド
def search[B >: A](x: B)(implicit f: B => Ordered[B]): Boolean =
if (isEmpty) false
else if (item == x) true
else if (x < item) left.search(x)
else right.search(x)
def insert[B >: A](x: B)(implicit f: B => Ordered[B]): ImTree[B] =
if (isEmpty) imNode(x, imEmpty, imEmpty)
else if (item == x) this
else if (x < item) imNode(item, left.insert(x), right)
else imNode(item, left, right.insert(x))
def delete[B >: A](x: B)(implicit f: B => Ordered[B]): ImTree[B] =
if (isEmpty) this
else if (item == x) {
if (left.isEmpty) return right
if (right.isEmpty) return left
return imNode(right.searchMin, left, right.deleteMin)
} else if (x < item) imNode(item, left.delete(x), right)
else imNode(item, left, right.delete(x))
引数 x に型パラメータ A を指定すると、共変のパラメータが反変の位置に出現してしまいます。このため、A を型パラメータ B に置き換えて、下限境界 >: A を設定します。また、型パラメータ B は比較演算子を使う必要があるので、暗黙のパラメータ f の型に B => Ordered[B] を指定します。これで値を比較するとき暗黙の型変換が行われます。insert と delete の返り値の型は ImTree[B] になります。
あとの修正は簡単なので説明は割愛します。詳細はプログラムリスト２をお読みください。
それでは実際に試してみましょう。
scala> :load imtree.scala // defined class ImTree // defined case class imNode // defined case object imEmpty scala> val a:ImTree[Int] = imEmpty.insert(5).insert(1).insert(9) val a: ImTree[Int] = imNode(5,imNode(1,imEmpty,imEmpty),imNode(9,imEmpty,imEmpty)) scala> val b:ImTree[Double] = imEmpty.insert(0.5).insert(0.1).insert(0.9) val b: ImTree[Double] = imNode(0.5,imNode(0.1,imEmpty,imEmpty),imNode(0.9,imEmpty,imEmpty)) scala> a.search(1) val res0: Boolean = true scala> a.search(10) val res1: Boolean = false scala> b.search(0.1) val res2: Boolean = true scala> b.search(0.0) val res3: Boolean = false scala> a.delete(5) val res4: ImTree[Int] = imNode(9,imNode(1,imEmpty,imEmpty),imEmpty) scala> b.delete(0.5) val res5: ImTree[Double] = imNode(0.9,imNode(0.1,imEmpty,imEmpty),imEmpty) scala> a.foreach(println) 1 5 9 scala> b.foreach(println) 0.1 0.5 0.9 scala> a.foldl((_:Int) + (_:Int), 0) val res8: Int = 15 scala> b.foldr((_:Double) + (_:Double), 0.0) val res9: Double = 1.5
正常に動作しているようです。興味のある方はいろいろ試してみてください。
//
// imlist.scala : immutable singly-linked list
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
// 連結リスト (抽象クラス)
abstract class ImList[+A] {
def isEmpty: Boolean
def car: A
def cdr: ImList[A]
def apply(n: Int): A =
if (isEmpty) throw new Exception("ImList.apply: out of range")
else if (n == 0) car
else cdr.apply(n - 1)
def insert[B >: A](n: Int, x: B): ImList[B] =
if (n == 0) Cons(x, this)
else if (isEmpty) throw new Exception("ImList.insert: out of range")
else Cons(car, cdr.insert(n - 1, x))
def delete(n: Int): ImList[A] =
if (isEmpty) throw new Exception("ImList.delete: out of range")
else if (n == 0) cdr
else Cons(car, cdr.delete(n - 1))
def length(): Int = if (isEmpty) 0 else 1 + cdr.length()
def positionIf(f: A => Boolean, i: Int = 0): Int =
if (isEmpty) -1
else if (f(car)) i
else cdr.positionIf(f, i + 1)
def map[B](f: A => B): ImList[B] =
if (isEmpty) Nils
else Cons(f(car), cdr.map(f))
def filter(f: A => Boolean): ImList[A] =
if (isEmpty) this
else if (f(car)) Cons(car, cdr.filter(f))
else cdr.filter(f)
def foldl[B](a: B, f: (B, A) => B): B =
if (isEmpty) a
else cdr.foldl(f(a, car), f)
def foldr[B](a: B, f: (A, B) => B): B =
if (isEmpty) a
else f(car, cdr.foldr(a, f))
def foreach(f: A => Unit): Unit = {
if (!isEmpty) {
f(car)
cdr.foreach(f)
}
}
}
// セル
case class Cons[A](item: A, next: ImList[A]) extends ImList[A] {
def isEmpty: Boolean = false
def car: A = item
def cdr: ImList[A] = next
}
// 終端 (空リスト)
case object Nils extends ImList[Nothing] {
def isEmpty: Boolean = true
def car = throw new Exception("ImList.car: Empty list")
def cdr = throw new Exception("ImList.cdr: Empty list")
}
//
// imtree.scala : immutable で多相型の二分探索木
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
// 二分木 (抽象クラス)
abstract class ImTree[+A] {
def isEmpty: Boolean
def item: A
def left: ImTree[A]
def right: ImTree[A]
def search[B >: A](x: B)(implicit f: B => Ordered[B]): Boolean =
if (isEmpty) false
else if (item == x) true
else if (x < item) left.search(x)
else right.search(x)
def insert[B >: A](x: B)(implicit f: B => Ordered[B]): ImTree[B] =
if (isEmpty) imNode(x, imEmpty, imEmpty)
else if (item == x) this
else if (x < item) imNode(item, left.insert(x), right)
else imNode(item, left, right.insert(x))
def searchMin: A =
if (isEmpty) throw new Exception("ImTree.searchMin: Empty Tree")
else if (left.isEmpty) item
else left.searchMin
def searchMax: A =
if (isEmpty) throw new Exception("ImTree.searchMin: Empty Tree")
else if (right.isEmpty) item
else right.searchMax
def deleteMin: ImTree[A] =
if (isEmpty) this
else if (left.isEmpty) right
else imNode(item, left.deleteMin, right)
def deleteMax: ImTree[A] =
if (isEmpty) this
else if (right.isEmpty) left
else imNode(item, left, right.deleteMax)
def delete[B >: A](x: B)(implicit f: B => Ordered[B]): ImTree[B] =
if (isEmpty) this
else if (item == x) {
if (left.isEmpty) return right
if (right.isEmpty) return left
return imNode(right.searchMin, left, right.deleteMin)
} else if (x < item) imNode(item, left.delete(x), right)
else imNode(item, left, right.delete(x))
def foldl[B](f: (B, A) => B, a: B): B =
if (isEmpty) a
else right.foldl(f, f(left.foldl(f, a), item))
def foldr[B](f: (A, B) => B, a: B): B =
if (isEmpty) a
else left.foldr(f, f(item, right.foldr(f, a)))
def foreach(f: A => Unit): Unit = {
if (!isEmpty) {
left.foreach(f)
f(item)
right.foreach(f)
}
}
def toList: List[A] =
if (isEmpty) Nil
else left.toList ::: (item :: right.toList)
}
// 節
case class imNode[A](item: A, left: ImTree[A], right: ImTree[A]) extends ImTree[A] {
def isEmpty: Boolean = false
}
// 終端 (空の木)
case object imEmpty extends ImTree[Nothing] {
def isEmpty: Boolean = true
def item = throw new Exception("item: Empty Tree")
def left = throw new Exception("left: Empty Tree")
def right = throw new Exception("right: Empty Tree")
}