LL脳がscalaの勉強を始めたよ その51
Scalaコップ本の16章にはいりますよー、16章はScalaで一番使われるデータ構造のリストについてですな
リストリテラル
リストの書き方は様々あるでよ！をざざっと
// Stringリスト val test = List("hoge", "huga", "moge") // Integerリスト val nums = List(1, 2, 3, 4) // Listリスト val lists = List( List(1,2,3), List(4,5,6), List(7,8,9) ) // 空リスト val empty = List()
リストの性質を箇条書きでー
- リストの要素は同じ型
- リストはイミュータブル（代入書き換え禁止）
- リストは再帰的な構造（配列はフラット）
んじゃ、リストの詳細を見ていきますよー
List型
リストの要素は全て同じ型なのですが、この性質をhomogeneousを呼ぶみたいです。ほんで、内部要素の型込みでのリスト型の表記はList[T](Tが要素型)になりますねー
さっき書いたリストサンプルを型定義込みで詳細に書きなおしてみます
// Stringリスト val test:List[String] = List("hoge", "huga", "moge") // Integerリスト val nums:List[Int] = List(1, 2, 3, 4) // Listリスト val lists:List[List[Int]] = List( List(1,2,3), List(4,5,6), List(7,8,9) ) // 空リスト val empty:List[Nothing] = List()
まあ、普段はコンパイラ様が型推論でうまい具合やってくれるので気にしないんですけど(・ε・)
ちなみにリストではList[S]とList[T]があった場合に、SがTのサブ型だったらList[S]もList[T]のサブ型になるみたいです。これを共変と呼ぶらしいですねー。具体的にはList[String]はList[Object]のサブ型とかとかデスネ。共変については19章で詳しくやるそうデス
Nothing型は前の方でもやったとおり全てのScala型のサブ型になるので、空リストオブジェクトは全てのリスト型のサブ型としてみることが出来るとのことです。例えばこんなさんぷるもかけちゃいマス
// Nothing型はString型のサブクラスでもあるので代入可能デス val test:List[String] = List()
リストの構築
さっきまでの例ではリストの初期化時に要素も突っ込んでましたが、リストはNil(空リスト)と::(cons)使って各要素を組み合わせることで構築することもできます。例えばx :: yとすることで要素をリスト的に結合することができます。なので空リストNilに各要素を結合していくことで新しいリストを構築できるワケですね。
まあ、文章でズラズラ書いても分かりにくいので上で書いたサンプルを構築バージョンに描き直してみますかねー
// Stringリスト // Nilはいちばんうしろに配置します val test = "hoge" :: "huga" :: "moge" :: Nil // Integerリスト val nums = 1 :: 2 :: 3 :: 4 :: Nil // Listリスト val lists = List( (1 :: 2 :: 3 :: Nil) :: (4 :: 5 :: 6 :: Nil) :: (7 :: 8 :: 9 :: Nil) :: Nil ) // 空リスト val empty = Nil
上のサンプルは::の右結合を上手く利用した省略型ですが、詳細に書くとこんな感じになりますねー
// 長くなるのでString結合だけです val test = "hoge" :: ("huga" :: ("moge" :: Nil))
実際のところval test = List("hoge", "huga", "moge")な形式は上の書き方のラッパーにすぎないそうです
リストに対する基本操作
リストの操作は次の3つによって表現できるそうです
- head:リストの先頭要素を返す
- tail:リストの先頭要素を覗く全ての要素から構成されるリストを返す
- isEmpty:リストが空ならtrueを返す
とりあえず試してみましょうかねー
// とりあえずリストを定義しますよ scala> val test = List("hoge", "huga", "moge") test: List[java.lang.String] = List(hoge, huga, moge) // 先頭要素をとってみます scala> test.head res6: java.lang.String = hoge // 先頭要素以外を返します scala> test.tail res7: List[java.lang.String] = List(huga, moge) // 2番目（先頭要素以外の中の先頭要素）の要素を返します scala> test.tail.head res8: java.lang.String = huga // 3番目の要素を返しますよ scala> test.tail.tail.head res9: java.lang.String = moge // 空かどうか判定しますよ scala> test.isEmpty res10: Boolean = false // tailの重ね掛けで空リストにしてやります scala> test.tail.tail.tail res11: List[java.lang.String] = List() // 空リストならisEmptyでtrueが返りますね scala> test.tail.tail.tail.isEmpty res12: Boolean = true
ちなみにtailやheadは空リストで使うとおこられますな
scala> Nil.head // 空リストだってば java.util.NoSuchElementException: head of empty list at scala.Nil$.head(List.scala:1365) 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(NativeMethodAccessorI... scala> Nil.tail // 空リストだって言ってるだろ(#ﾟДﾟ) java.util.NoSuchElementException: tail of empty list at scala.Nil$.tail(List.scala:1367) 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(NativeMethodAccessorI...
headとtailとisEmptyで昇順ソート
リスト処理の具体例としてList[Int]の昇順ソートを書いてみますよー、アルゴリズムは挿入ソートです。
// 挿入ソートで数値リストを昇順ソート def isort(xs:List[Int]):List[Int] = { // 空リストの場合は終了 if(xs.isEmpty) Nil // 空リストでない場合は挿入ソートを実行 else insert(xs.head, isort(xs.tail)) } // 挿入ソートアルゴリズムを定義 def insert(x:Int, xs:List[Int]):List[Int] = { // 挿入先リストが空の場合 // または先頭の数よりも小さい場合は先頭に追加 if(xs.isEmpty || x <= xs.head) x :: xs // 先頭の数より大きい場合は先頭以外の要素で再帰的に処理 else xs.head :: insert(x, xs.tail) } // 実行します scala> isort(List(3,3,4,5,6)) // ソートできましたよ(｀・ω・´) res18: List[Int] = List(3, 3, 4, 5, 6) ||< 小さい要素が先頭に来るように比較して結合し続けるような動作ですね。与えられた新要素が先頭よりも大きい場合は構築中リストから”先頭以外リスト”を構築して再度比較して...を繰り返すイメージですな、なるほどΣ( ﾟДﾟ) ** リストパターン パターンで分解することでリストの各要素にアクセスすることができるみたいです >|scala| // リスト定義です scala> val test = List(1,2,3) test: List[Int] = List(1, 2, 3) // 各要素をパターンで分解しましたよ scala> val List(a,b,c) = test a: Int = 1 b: Int = 2 c: Int = 3
ただし上記パターンだと要素数をあわせなければエラーになりますな
scala> val List(a,b) = test scala.MatchError: List(1, 2, 3) at .<init>(<console>:9) 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) at sun.reflect.DelegatingMethodAccessorImpl....
もし要素数が不明で先頭の要素だけ取り出した時なんかは::を使ってマッチさせるのがいいみたいです
scala> val test = List(1,2,3) test: List[Int] = List(1, 2, 3) // 先頭1要素だけマッチしますよ scala> val a :: other = test a: Int = 1 other: List[Int] = List(2, 3) // 先頭2要素だけマッチさせます scala> val a :: b :: other = test a: Int = 1 b: Int = 2 other: List[Int] = List(3)
ただし最後の1要素とかはどうあがいても無理そうですな、たぶん内部的にtailメソッド使ってるからしょうがないんだろうな
scala> val other :: (b :: c) = test other: Int = 1 b: Int = 2 // 最後の位置要素はどうしてもリストになってしまいますな c: List[Int] = List(3) // まあ要素数 + 1とかすればとれなくもないけども // 余り意味ない気もする(´・ω・｀) scala> val other :: b :: c :: d = test other: Int = 1 b: Int = 2 c: Int = 3 d: List[Int] = List()
ちなみに::もList(a, b, c)も前章のパターンマッチでは扱わなかったのですが、::はScala.::クラス(::にはscala.::とListクラスの::の2通りがあるらしいです)によるコンストラクタパターンが適用されて、List(a, b, c)はライブラリ定義の抽出子パターンみたいです。詳しくはそれぞれ22章と24章でやらしいので細かいところはおいておきますよー
挿入ソートをパターンで
パターンを使うとhead, tail, isEmpty等の基本メソッドを使わなくてもリストの分解ができるので結構わかりやすくなりそうですな
試しに先程やった挿入ソートをパターンマッチを使って書いてみるサンプルです
// ソート実行関数デス def isort(xs:List[Int]):List[Int] = xs match { case Nil => Nil case x :: xs => insert(x, isort(xs)) } // 挿入ソートアルゴリズムです def insert(x:Int, xs:List[Int]):List[Int] = xs match { case Nil => Nil // 再帰でパターンマッチ処理をします case y :: ys => if(x <= y) x :: xs else y :: insert(x, ys) }
うん、だいぶScalaになれてきたこともあってパターンマッチの方が解りやすい気がする(｀・ω・´)この調子で頑張ろう
