LL脳がscalaの勉強を始めたよ その73
Scalaコップ本19章の続きををやりますよ。今回で終わりにしたい19章は型パラメータについてやっております(´・ω・｀)
ちなみに19章でサンプルとして扱ってきた関数型待ち行列クラスQueueは次のような感じです
// 外部からアクセスすための公開インターフェースとしてのトレイト trait Queue[T]{ def head:T def tail:Queue[T] def append(x:T):Queue[T] } // クラス実装自体を格納するオブジェクトです object Queue{ // 待ち行列クラスの実装を行う非公開クラスです private class QueueImpl[T]( private val leading:List[T], private val trailing:List[T] // トレイトミックスインです ) extends Queue[T]{ def mirror = { if(leading.isEmpty) new QueueImpl(trailing.reverse, Nil) else this } def head:T = mirror.leading.head def tail:QueueImpl[T] = { val q = mirror new QueueImpl(q.leading.tail, q.trailing) } def append(x:T) = new QueueImpl(leading, x::trailing) } // オブジェクト生成用のapplyメソッドデス def apply[T](xs:T*):Queue[T] = new QueueImpl[T](xs.toList, Nil) }
オブジェクト非公開データ
19章で徐々に構築してきたQueueクラスにはleadingが空になっている状態でheadが連続して呼び出されると、trailingとleadingの同期を取るためにmirrorメソッドががtrailingをleadingに繰り返しコピーしてしまうという問題があるのデス(´・ω・｀)。今回はこのような無駄処理を副作用を使って避けることにしてみます。
とりあえずheadの呼び出しによる無駄なコピーを防ぐ実装はこんな感じになりますね
class Queue[+T] private ( // 再代入可能な形式で定義 private[this] var leading:List[T], private[this] var trailig:List[T] ){ // 同期用のmirrorメソッドは副作用によって // leadingとtrailingの同期を行なうのです(´・ω・｀) private def mirror() = { if(leading.isEmpty){ // trailingからleadingへの反転コピーを行ないますデス while(!trailing.isEmpty){ leading = trailing.head :: leading // この結果trailingの値がなくなりますが、今回定義するメソッドの中で // 演算関係性がきちんと閉じているので無問題っぽいっす(´・ω・｀) trailing = trailing.tail } } } // 先頭の値を返しますよ def head:T = { mirror() leading.head } // 先頭以外の値で構成されたQueueオブジェクトを返します def tail:Queue[T] = { mirror() new Queue(leading.tail, trailing) } // あたらしくQueueに要素を追加します def append[U >: T](x: U) = new Queue[U](leading, x::trailing)
副作用を利用することによって無駄なコピー（新しいイミュータブル変数の生成）を防止することができました。
上記のように修正を行った結果、Queueクラスはミュータブルフィールドを持つようになったのですがleadingとtrailingは非公開変数なので外からはこれらによる副作用は見えないのです。なので外見からのこいつは純粋関数型オブジェクトを定義してるのと変わらないんだぜ！とはコップ本曰くデス(´・ω・｀)…まあ確かにそうだけどさ
改造Queueは型チェックをパスするのか？
新しいコードではシレッとT型の共変パラメータをとる再代入可能なフィールドを追加しているのですが、leadingとtrailingはprivate[this]修飾子でオブジェクト非公開宣言をしているので規則違反にはならないそうです。
これはオブジェクト非公開メンバーは定義されたオブジェクト以外からのアクセスが出来ないわけで、また定義したオブジェクトの変数からのアクセスにとっては変位指定に関する諸問題は無関係なものとなるとのことです。
これは変位指定が型エラーを引き起こすような条件を作り出すためには、オブジェクトの定義型よりも静的に弱い方を持つ包含オブジェクトへの参照が必要らしいのですが、非公開オブジェクトの値へのアクセスではそもそも起こりえないからだそうです(´・ω・｀)
うん、写経終了(´・ω・｀)あとでちゃんとやり直そう
上限境界
トレイトのメソッドに渡されるパラメータの要素型がそのトレイトのサブ型であるように強制指定するには上限境界を利用するらしいです。
とりあえず次のようなPersonクラスに対してScala組み込みのOrderedトレイトをミックスインしたものを考えてみますね。
class Person(val firstName: String, val lastName:String) extends Ordered[Person] { // 抽象メソッドcompareを実装すると // クラスのインスタンスを<,>,<=,>=演算子で比較できるようになるらしいです def compare(that:Person) = { // 大小関係は辞書的にどちらが大きいか比較することで決定しますネ(´・ω・｀) // まずは苗字で比較しますよ val lastNameComparison = lastName.compareToIgnoreCase(that.lastName) // 結果が出なければ名前で比較デス if(lastNameComparison != 0) lastNameComparison else firstName.compareToIgnoreCase(that.firstName) } override def toString = firstName + " " + lastName } //// とりあえず実行してみますかね // 高橋太郎さんを定義します scala> val taro = new Person("Takahashi", "Taro") taro: Person = Takahashi Taro // 鈴木次郎さんを定義します scala> val jiro = new Person("Suzuki", "Jiro") jiro: Person = Suzuki Jiro // 比較してみますよ scala> taro < jiro res1: Boolean = false // 太郎さんの方が辞書的に大きいみたいですね scala> taro > jiro res2: Boolean = true
上限境界を導入したマージソート
それでは、パラメータとして渡されるリストにOrderedトレイトをミックスイン指定なければダメYO！と指定するために上限境界を導入したソート関数を作成しますよ(´・ω・｀)上限境界は < :記号を使って T
def orderedMergeSort[T <: Ordered[T]](xs:List[T]):List[T] = { // マージ処理です def merge(xs:List[T], ys:List[T]):List[T] = { // パターンマッチで振り分けます (xs, ys) match { // 片方が空だったら空ではない方を返しますね case (Nil, _) => ys case (_, Nil) => xs // 先頭要素が大きい方をとって、更にマージ処理します case (x::xs1, y::ys1) => { if (x < y) x :: merge(xs1, ys) else y :: merge(xs, ys1) } } } // マージソートなので要素の中心をゲットしますね val n = xs.length / 2 // 要素がある場合のみ処理をしますです if (n == 0) xs else { // 要素を半分にして処理を適用、って流れを再帰的に行ないます val (ys, zs ) = xs splitAt n merge(orderedMergeSort(ys), orderedMergeSort(zs)) } }
マージソートの詳しいアルゴリズムについては（以前やったようなきがするけども）とりあえずwikipedia:マージソートをご参照アレ(｀・ω・´)
上限境界を設定することで、orderedMergeSortに渡されるリストの要素型がOrderedのサブ型になる必要があるように設定することが出来るようになります。ちなみにPersonクラスはOrderedトレイトをミックスインしているのでOrderedのサブ型とみなせるそうですｃ⌒っﾟдﾟ)っφ ﾒﾓﾒﾓ...
とりあえず、今回利用したいリストはこんな感じですね
val people = List( new Person("Takashashi", "Taro"), new Person("Suzuki", "Jiro"), new Person("Sato", "Saburo"), new Person("Honda", "Siro"), new Person("Yoshida", "Goro") )
こいつらをorderedMergeSortに渡しますよ
scala> val sortedPeople = orderedMergeSort(people) // おお、ソートされております sortedPeople: List[Person] = List(Yoshida Goro, Suzuki Jiro, Sato Saburo, Honda Siro, Takashashi Taro)
サブ型以外は拒否します
ちなみにOrderedのサブ型以外を渡すと、次のようにきっちり怒られますな(´・ω・｀)
scala> val errorSort = orderedMergeSort(List(1,2,3,4,5)) <console>:5: error: inferred type arguments [Int] do not conform to method orderedMergeSort's type parameter bounds [T <: Ordered[T]] val errorSort = orderedMergeSort(List(1,2,3,4,5)) ^
上限境界はライブラリなんかを作るときのパラメータチェックに重宝しそうです(｀・ω・´)
