LL脳がscalaの勉強を始めたよ その52
Scalaコップ本の16章の続きをやっていきますよー、今回はリストの具体的操作として Listクラスの一階メソッドをやっていきますよー。この節は量が多いので半分ずつで２回に分けます
ちなみに一階メソッドはパラメーターとして関数を取らないものらしいです。
リストの連結
リスト同士の連結は ::: で行ないマス、とりあえずサンプルやってみますかね
// 結合します scala> List(1,2) ::: List(1,2,3) res1: List[Int] = List(1, 2, 1, 2, 3) // 空リストと結合しますよ scala> List() ::: List(1,2,3) res2: List[Int] = List(1, 2, 3) // 逆方向に空リストと結合しマス scala> List(1,2) ::: List() res3: List[Int] = List(1, 2) // Int要素とString要素のリストを結合します scala> List(1,2) ::: List('a','b') // 動的型変換でList[AnyVal]型に変換されました res5: List[AnyVal] = List(1, 2, a, b)
ちなみに３つ以上の結合は後ろから順に処理されるみたいです
// 3つの連結は scala> List(1,2) ::: List(3,4) ::: List(5,6) res6: List[Int] = List(1, 2, 3, 4, 5, 6) // ::: 右結合なのでこういうふうに解釈されマス scala> List(1,2) ::: (List(3,4) ::: List(5,6)) res7: List[Int] = List(1, 2, 3, 4, 5, 6)
分割統治原則
連結(:::)の処理の仕組みを理解するために、同じような処理をappendメソッドとして実装してみましょうー、具体的には再帰的なパターンマッチで片方のリスト要素を他方のリスト要素に加えていくような操作になりますかね
注意したほうがよさそうなのは次の２つみたいですねー
- リストの要素型は何が来てもいいように型パラメータTを利用する
- 再帰的データ構造を操作するための分割統治原則
型パラメータについては、いまのところはどんな型も受け入れるぜ（ただし要素型は一致する前提でな）ヒャッハーくらいに抑えておきますデス。詳しいことは19章でやるらしいので。
そんで分割統治原則ですが、単純なケースに"分割"する→結果値がからでなければ同じアルゴリズムを再帰的に呼び出す、という一連の流れで組み立てることみたいです。まあ原則というか指針というかそんな感じに解釈して実際の処理をかいてみますかねー
では:::の独自実装appendはこんな感じですかねー
// 2つのListを引数にとった関数を定義しますよ // 具体的には第一パラメータのリストにたいするパターンマッチで処理します def append[T](xs: List[T], ys:List[T]):List[T] = xs match { // 第一パラメータのリストが空の場合は第2パラメータをそのまま返します case List() => ys // 第一リストの先頭要素を抜き出して // それ以外の要素で構成されるリストと第2リストで再処理します case x :: xs1 => x :: append(xs1, ys) }
んじゃ実行してみますよー
// 結合してみます scala> append(List(1,2), List(3,4)) res12: List[Int] = List(1, 2, 3, 4) // 空リストとも結合してみますよ scala> append(List(), List(3,4)) res13: List[Int] = List(3, 4) // 空リスト同士でもOKですね scala> append(List(), List()) res14: List[Nothing] = List() // 動的型変換もしてくれましたな scala> append(List(1,2), List('a','b')) res16: List[AnyVal] = List(1, 2, a, b)
だいたいこんな感じですね。とりあえず分割統治原則は何度も繰り返されてて大事そうなのでｃ⌒っﾟдﾟ)っφ ﾒﾓﾒﾓ...
リストの長さを計算するlength
他の言語でもよくでてくるやつですねー、長さというか要素数の計算です。とりあえずサンプルはこんな感じです
// ()は付けないです scala> List(1,2,3,4,5).length res21: Int = 5
ちなみにリストはデータの構造上、長さ計算を行う場合にリスト全体をたどる必要があるのでlength処理は比較的コストが高いらしいです。なのでisEmptyを.length == 0で置き換えたりすんな、な (#ﾟДﾟ)!との念押しをされました。
リストの末尾へのアクセス:initとlast
リストの基本操作でhead(先頭を取り出す)とtail(先頭以外の要素で構成されたリストを返す)をやったのですが正反対の性質をもつlastとinitについてサンプル書いてみます
// last最後の要素を取り出します scala> List(1,2,3,4,5).last res23: Int = 5 // initは最後以外の要素で構成されたリストえお返しますよー scala> List(1,2,3,4,5).init res24: List[Int] = List(1, 2, 3, 4)
ちなみに両方ともに空リストで使用すると例外投げまくりなので注意です
// 空last scala> List().last java.util.NoSuchElementException: Nil.last at scala.List.last(List.scala:641) at .<init>(<console>:5) at .<clinit>(<console>) at RequestResult$.<init>(<console>:3) at RequestResult$.<clinit>(<console>) at RequestResult$result(<console>) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57... // 空init scala> List().init java.lang.UnsupportedOperationException: Nil.init at scala.List.init(List.scala:622) at .<init>(<console>:5) at .<clinit>(<console>) at RequestResult$.<init>(<console>:3) at RequestResult$.<clinit>(<console>) at RequestResult$result(<console>) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl....
ついでに、lastもinitもリスト全体をたどって処理するのでコスト高めみたいです。なのでデータ構造を設計する場合はリストの末尾ではなく先頭にアクセスするようにすると良いみたいですねー
ちなみにhead ⇔ last、tail ⇔ initみたいな関係を相対的な捜査(dual operation)というみたいです。ちょい厨二風味で素敵な関係です(｀・ω・´)トカ思うのはダメですか？
リストの反転:reverse
リストの要素の順序を反転するのにはreverseを使うのがよさげです。とりあえずサンプルやってみますよー
// 反転しますねー scala> List(1,2,3,4,5).reverse res28: List[Int] = List(5, 4, 3, 2, 1)
ちなみにここで使っているListはimmutableなのでreverseで反転されるリストは新しく生成されたものですな
// リストの生成しますよ scala> val l = List(1,2,3,4,5) l: List[Int] = List(1, 2, 3, 4, 5) // 反転してみます scala> l.reverse res29: List[Int] = List(5, 4, 3, 2, 1) // 反転されたのは新しく生成されたリストなので元のリストはそのままです scala> l res30: List[Int] = List(1, 2, 3, 4, 5)
例えば処理の都合上リストの末尾へのアクセスが頻繁に発生してしまう場合などは反転したリストをもう一個作ってしまえば効率的だったりするのですが、そんなときこそreverseの出番みたいですね
reverseで法則確認
んじゃ、せっかくなのでreverseを使ってちょっと遊んでみます
まずはreverseの重ねがけで元に戻してみます
// reverseは自身への逆操作なので反転の反転で元に戻ります scala> List(1,2,3).reverse.reverse == List(1,2,3) res31: Boolean = true
次にreverseでinit ⇔ tail, last ⇔ headを確認してみますよ。最初にinitとtailです（要素の順序は逆ですが、要素は同じという確認です）
// tailはinitの逆 scala> List(1,2,3).tail res38: List[Int] = List(2, 3) scala> List(1,2,3).reverse.init res39: List[Int] = List(3, 2) // initはtailの逆 scala> List(1,2,3).init res40: List[Int] = List(1, 2) scala> List(1,2,3).reverse.tail res41: List[Int] = List(2, 1)
次にlastとheadですね
// lastはheadの逆です scala> List(1,2,3).last == List(1,2,3).reverse.head res47: Boolean = true // headはlastの逆ですけども scala> List(1,2,3).head equals List(1,2,3).reverse.last res48: Boolean = true
こんな感じですねー
連結を使ってreverseを実装
reverse絡みでもういっちょ、連結処理を使ってreverseを実装してみますよ
reverseの独自実装revは先程の:::の独自実装と同様にパターンマッチと再帰を使って次のようになりますねー
def rev[T](xs:List[T]):List[T] = xs match { // 空ならそのまま case List() => xs // 先頭要素を後ろにおいて残った要素についても // 再帰で同様の処理を継続 case x :: xs1 => rev(xs1) ::: List(x) } // 実行結果です scala> rev(List(1,2,3)) res50: List[Int] = List(3, 2, 1)
ちなみに上記独自実装の計算量は入力Listの長さの2乗に比例するので、reverseに比べてもコスト悪過ぎのため使えないです(´；ω；｀) 、あまりにもひどいのでこの後の節で若干高速化してみます。
現在の計算量はこんな感じです
// 1回目の処理、連結の計算量はパラメータxsの長さ(n) n // 2回目の処理、連結の計算量はパラメータxs1の長さ(n - 1) + ( n - 1) // そんな感じでxsの要素個数(n)分繰り返し + ... +1 // まとめるとこんな感じ = ( 1 + n ) * n /2
ちなみにreverseのコストはListの要素数に比例するそうデス
プレフィックスとサフィックス:drop,take,splitAt
takeとdrop
tailやinitはそれぞれ「先頭以外」・「末尾以外」の要素から構成されたListを返しますが、これを一般化したものとしてtakeとdropがあるみたいです。
// takeは先頭n個の要素を返しますよ(nは引数) scala> List(1,2,3).take(2) res51: List[Int] = List(1, 2) // dropは先頭n個以外の要素を返しますよ(nは引数) scala> List(1,2,3).drop(2) res52: List[Int] = List(3)
ちなみにパラメータが要素数よりおおきくてもきちんと処理してくれるみたいですね
// takeは全ての要素が含まれたListを返しマス scala> List(1,2,3).take(4) res56: List[Int] = List(1, 2, 3) // dropは空リストを返しますね scala> List(1,2,3).drop(4) res57: List[Int] = List()
splitAt
リストを特定の位置で分割したい場合なんかはsplitAtを使うみたいです。splitAtでは渡された添字の位置でリストを分割して結果をペア（タプルで返します）
// 1番目の要素で分割 scala> List(1,2,3).splitAt(1) res59: (List[Int], List[Int]) = (List(1),List(2, 3)) // 2番目の要素で分割 scala> List(1,2,3).splitAt(2) res60: (List[Int], List[Int]) = (List(1, 2),List(3)) // リストサイズよりも大きい位置で分割したらこんな感じ scala> List(1,2,3).splitAt(5) res61: (List[Int], List[Int]) = (List(1, 2, 3),List())
ちなみにsplitAtをtakeとdropを使って実装するとこうなりマス
scala> (List(1,2,3).take(2), List(1,2,3).drop(2)) == List(1,2,3).splitAt(2) res62: Boolean = true
