LL脳がscalaの勉強を始めたよ その55
Scalaコップ本16章の続きをやっていきますよ、今回はパラメータに関数をとる高階メソッドの後半からやっていきます(゚Д゚)ノ
リストを対象とする述語関数:foralとexists
指定条件に適合する要素が一つでも存在するかどうかを判定するexistsと、全ての要素が条件に適合するかどうかを判定するforallデス
とりあえず、まあ、サンプルです
// 0が要素に一つでもあればTrueですね scala> List(0,1,2,3,4,5).exists(_ == 0) res6: Boolean = true // 0が要素にないのでfalseです scala> List(1,2,3,4,5).exists(_ == 0) res7: Boolean = false // 全ての要素が0ならばTrueデス scala> List(0,0,0,0,0).forall(_ == 0) res8: Boolean = true // 0でない要素が一つでも存在すればFalseデス scala> List(0,0,1,0,0).forall(_ == 0) res9: Boolean = false
要素チェックなんかに使う感じですかね(´・ω・`)
リストの畳込み: /:と:\
なんだか顔文字みたいなやつですが畳込み演算というヤツみたいですが、リストから2つの要素を抜き出して二項演算を行うメソッドみたいです。ちなみに/:が左畳込みで、:\が右畳込みみたいです。
左畳込み
(z /: list) (二項演算)の形式で使用します。演算順序は次のようになるみたいです。
- zとリストの第1要素での演算
- 上記結果とリストの第2要素で演算
- (以下繰り返し)
実際の演算はこんな感じに解釈できますかねー
(z /: List(a, b, c)) (op) → op(op(op(z, a), b), c)
んじゃ実際に使ってみますよ
scala> ( 0 /: List(1,2,3,4,5))(_ + _) res15: Int = 15
左畳込みは左に初回パラメータを付与することを忘れずに(`・ω・´)ですね
右畳込み
左畳込みとは逆に右側から演算するヤツです。演算イメージとしてはこんな感じですね
(List(a, b, c) :\ z) (op) → op(a, op(b, op(c, z)))
んじゃこっちも試し実行してみますよ
scala> (List(1,2,3,4,5) :\ 0)(_ + _) res18: Int = 15
畳込みでflattenメソッドを実装
List[List[Any]]形式のリスト内全リストの全要素を連結するList.flattenメソッドを左・右の両畳込みで実装してみますよ。とりあえずflattenメソッドはこんな感じの動作ですね
scala> List.flatten(List(List(1,2,3), List("a","b","c"))) res27: List[Any] = List(1, 2, 3, a, b, c)
とりあえず左畳込みで実装してみますよ
scala> (List[Any]() /: List(List(1,2,3), List("a", "b", "c"))) ( _ ::: _) res30: List[Any] = List(1, 2, 3, a, b, c)
次に右畳込みで実装してみますかね
scala> (List(List(1,2,3), List("a", "b", "c")) :\ List[Any]()) ( _ ::: _) res31: List[Any] = List(1, 2, 3, a, b, c)
ちなみに ::: による連結は第1パラメータの長さに比例して計算量が増えるみたいなので、第1パラメータに対して常にひとつの要素を渡す右畳込み式flattenのほうが効率が良いみたいです。
また両方とも第一演算要素として空リストを渡す際に型アノテーション(ここでは簡略化としてList[Any]にしていますが、コップ本では関数化した上でList[T]形式で使ってます)を使用しているのはコンパイラの型推論が上手く働かないからみたいです。
// 型エラーです scala> (List() /: List(List(1,2,3), List("a", "b", "c"))) ( _ ::: _) <console>:5: error: type mismatch; found : List[Any] required: List[Nothing] (List() /: List(List(1,2,3), List("a", "b", "c"))) ( _ ::: _) ^ // こちらも型エラーです scala> (List(List(1,2,3), List("a", "b", "c")) :\ List()) ( _ ::: _) <console>:5: error: type mismatch; found : List[Any] required: List[Nothing] (List(List(1,2,3), List("a", "b", "c")) :\ List()) ( _ ::: _) ^
なんで型推論が失敗するのか?については22章で詳しくやるそうです(´・ω・`)
ついでに/:や:\みたいなヘンテコ記号を使いたくない人はfoldLeftやfoldRightっていう別名あるからそっち使えYO!だそうです。設計者的には記号の方が木構造との対応関係が解りやすいよね?ってアピールしたいらしいんですが…まあいろいろあったんでしょうな(´・ω・`)
foldを使ったリストの反転
foldLeftを使って効率的なreverseメソッドを実行しようぜ!ということでやってみます。ちなみに以前実装したのはこんな感じでしたが、計算量がリストの長さの2乗…というたいへん効率の悪いものでした(´;ω;`)
def rev[T](xs:List[T]):List[T] = xs match { // 空ならそのまま case List() => xs // 先頭要素を後ろにおいて残った要素についても // 再帰で同様の処理を継続 case x :: xs1 => rev(xs1) ::: List(x) }
とりあえずサンプルやってみますかね
// 渡されたリスト要素を後ろに結合していく感じでリストを構築しますね def reverseLeft[T](xs:List[T]) = (List[T]() /: xs){(ys,y) => y :: ys} // 実行結果ですよ scala> reverseLeft(List(1,2,3,4,5)) res35: List[Int] = List(5, 4, 3, 2, 1)
この方式だと各結合処理が要素分しか行われないので、計算量がリストの長さに比例する程度で抑えられるみたいです
ついでに(::: 演算的に)若干効率はおちますが右畳込みでも実装してみましたよ
def reverseRight[T](xs:List[T]) = (xs :\ List[T]()){(ys,y) => y ::: List(ys)} // 実行結果ですよ scala> reverseRight(List(1,2,3,4,5)) res38: List[Int] = List(5, 4, 3, 2, 1)
リストのソート
高階メソッドの最後にリストのソートについてやりますよ。ソートを行う場合はsortメソッドに比較式を適用してこんな感じに行うみたいですね
// 昇順ソートです scala> List(1,4,2,5,6,8,3).sort(_ < _) res39: List[Int] = List(1, 2, 3, 4, 5, 6, 8) // 降順ソートですね scala> List(1,4,2,5,6,8,3).sort(_ > _) res40: List[Int] = List(8, 6, 5, 4, 3, 2, 1)
若干複雑に、例えば文字列の長さでソート!とかの場合はこんな感じですかね
// 文字列長で昇順ソートです scala> List("one", "two", "three", "four", "five").sort(_.length < _.length) res43: List[java.lang.String] = List(two, one, four, five, three) // 文字列長で降順ソートです scala> List("one", "two", "three", "four", "five").sort(_.length > _.length) res44: List[java.lang.String] = List(three, four, five, two, one)
蛇足で蛇足
sortメソッドにわたすパラメータはは論理演算の形式(true or false)なのでこんな処理もかけるみたいです。まあ、実用性はまったくないのですが…
// 比較要素が等しくないとtrueがわたるので // 常に並び順が正しいことになって渡された順が保持されます scala> List("one", "two", "three", "four", "five").sort(_.length != _.length) res45: List[java.lang.String] = List(two, one, four, five, three) // 常に並び順がfalseになるので並び替えが常に実行された結果です scala> List("one", "two", "three", "four", "five").sort(_.length == _.length) res46: List[java.lang.String] = List(four, two, three, five, one)
まあ処理的に意味はないのですが、ソートの適用順序とかが垣間見えるようで面白いなぁ…と
いじょうー
も少し行けるかと思ったけどタイムアップでココマデです。次回はリストオブジェクトのメソッドからやりますよ。次で16章終われるといい…なぁ(´・ω・`)