16. Working with Lists
Listはscalaで一番良く使うデータ型。
多くの一般的な操作をList上で実行することが出来る。
更に、Listを扱う上での重要な設計テクニックについても学ぶ。
16.1 List literals
ListはArrayと似ているが、違う点もある。
Listはimmutable, Arrayはmutable
Listはrecursive structure, Arrayはflat
i.e., a linked list
?? ArrayもArrayの中にArrayをnest出来るが、それでは再帰構造とは言えない??
16.2 The List type
Listはhomogeneous
Arrayと同じ。
各要素が同じ型。
List[T]でTが型
val l: List[List[Int]] = List(List(1, 2, 3), List(4,4))
** 要素数と型は無関係。
scalaではListの型はcovariant(共変)
SがTのsubtypeならList[S]もList[T]のsubtypeになる
ex. List[String]はList[Object]のsubtype
空のList()はList[Nothing]型
Nothingは全ての型のサブタイプ。Section 11.3
List[Nothing]も全ての型のサブタイプ。
List()は全てのList型の変数に代入可能。
val xs: List[String] = List()
16.3 Constructing lists
全てのListは二つの基礎的な構成要素から出来ている。
Nil -> 空リスト
:: -> cons、x :: xsでリストxsの先頭に要素xを付け加えたリストを表す。
List() == Nil
List(1, 2, 3) == 1 :: (2 :: (3 :: Nil)) == 1 :: 2 :: 3 :: Nil
::は:で終わる演算子なので右結合なので()を省略しても同じ意味。
?? これが再帰的構造と言う意味か ??
List(...)は::とNilの組み合わせのwrapperに過ぎない。
16.4 Basic operations on lists
Listの操作は下記の3つに集約される。
head, tail, isEmpty
headとtailを空のListに適用すると例外が投げがれる。
scala> Nil.head
java.util.NoSuchElementException: head of empty list
scala> Nil.tail
java.lang.UnsupportedOperationException: tail of empty list
16.5 List patterns
Listの要素を取り出すのにpattern matchingが使える。
val l = List(1, 2, 3)
val List(a, b, c) = l // a=1, b=2, c=3
val a :: b :: rest = l // a=1, b=2, c: List[Int] = List(3)
val x :: xs = l // x = l.head, xs = l.tail
head, tail, isEmptyを使うよりもpattern matchingを使うことを推奨。
より簡素で分かりやすくなる場合が多い。
** CourseraのWeek1の課題もpattern matchingを使えば簡素化出来る！！
About pattern matching on Lists
List(...)も::もChapter 15の可能なパターンに入っていない。
実際はextractorライブラリで定義されているinstanceのパターン。
x :: xsは::(x, xs)でpattern matchingの場合はconstructorとして扱われる。
::はclass scala.::のconstructorとclass Listのmethodの両方に定義されている。
Listの詳しい実装はChapter 22, extractorはChapter 24参照。
16.6 First-order methods on class List
first-order methods
関数を引数に取らないmethod。
高階method(higher-order methods)の逆。
Concatenating lists
::: -> List同士の結合
scala> List(1, 2) ::: List(3, 4, 5)
res0: List[Int] = List(1, 2, 3, 4, 5)
:で終わるので右結合
The Divide and Conquer principle
分割統治法
Listのような再帰的なデータ構造を扱う場合に良く使われる戦略
最初にpattern matchを使ってより単純なケースに入力を分割する。
各分割の演算結果を再帰呼び出しを使って結合する。
def append[T](xs: List[T], ys: List[T]): List[T] = xs match {
case List() => ys
case x :: xs1 => x :: append(xs1, ys)
}
xs, ysどちらを分割するかは、::で生成を考えるとxsで決まり。
分割の仕方は、空の場合とそれ以外に分けるパターンが多い。
リストを生成する場合、何がheadで何がtail化かを考えると良い。
Taking the length of a list: length
Listのlengthを求めるのは要素数に比例したコストが掛かる。
要素を走査する必要があるため。
Arrayの場合は不要。コストが低い。
isEmptyの変わりにlength == 0を使うべきではない。
Accessing the end of a list: init and last
last -> 最後の要素を返す。headの反対。
init -> 最後の要素を除いたリストを返す。tailの反対。
head, tailは固定時間で終わるが、last, initは要素数に比例した時間が掛かる。
リストの前の方にアクセスが集中する様なデータ設計が望ましい。
Reversing lists: reverse
reverseに関しては下記の推論が成り立つので、プログラムを簡略化に使える。
xs.reverse.reverse equals xs
xs.reverse.init equals xs.tail.reverse
xs.reverse.tail equals xs.init.reverse
xs.reverse.head equals xs.last
xs.reverse.last equals xs.head
reverseは下記で実装できるが、別の実装で性能を改善出来る。
この実装だとorder(n*n)。これをorder(n)に改善する。Section 16.7
def rev[T](xs: List[T]): List[T] = xs match {
case List() => xs
case x :: xs1 => rev(xs1) ::: List(x)
}
Prefixes and suffixes: drop, take and splitAt
xs take n -> 最初のn個の要素を含むリスト
xs drop n -> 最初のn個を取り除いたリスト
n > xs.length でも n < 0 でもOKで例外は投げない。
xs splitAt n equals (xs take n, xs drop n)
n個目の要素の前後でリストを分割する。
Element selection: apply and indices
Listのapplyはn番目の要素を返す。
abcde apply 2 // -> c
abcde(2) // -> c
scalaではArrayと違ってあまり使われない。
要素にアクセスするのに捜査が必要でnに比例した時間が掛かるから。
実装は下記と同じ。
xs apply n equals (xs drop n).head
indicesでインデックスのリストが得られる。
scala> abcde.indices
res13: List[Int] = List(0, 1, 2, 3, 4)
Zipping lists: zip
二つのリストから要素のタプルのリストを作成する。** 縦横変換。
scala> val zipped = abcde zip List(1, 2, 3)
zipped: List[(Char, Int)] = List((a,1), (b,2), (c,3))
長さが異なる時は短い方に丸められる。
使用頻度の高い特別なケースが値とindexを組みにする事。zipWithIndex
scala> abcde.zipWithIndex
res15: List[(Char, Int)] = List((a,0), (b,1), (c,2), (d,3), (e,4))
Displaying lists: toString and mkString
xs mkString (pre, sep, post)
scala> abcde mkString ("[", ",", "]")
res17: String = [a,b,c,d,e]
xs mkString sep equals xs mkString ("", sep, "")
xs mkString equals xs mkString ""
xs toString equals xs mkString ("List(", ", ", ")")
scala> abcde.toString
res16: String = List(a, b, c, d, e)
xs addString (buf, pre, sep, post)
?? 文字列そのもではなくてStringBuilder objectに付け加える ??
Listはtraite Iterableを継承しているので、Iterableな事に適用可能。
Converting lists: elements, toArray, copyToArray
toArray, toListでList<->Array間の変換が出来る。
xs copyToArray (arr, start)
arrのstart番目からxsの要素をすべてコピーする。
arrは使う側が十分な大きさを確保しておく必要がある。
xs.elements でiteratorにアクセスできる。
it = xs.elements; it.next; it.next...
Example: Merge sort
分割統治のカリー化の例としてmerge sortを扱う。
またアルゴリズムの複雑度(order)についても議論する。
merge sortのorderはn*log(n)で入力データによらない。
最悪値も平均値もorder(n*log(n))になる。
これがmerge sortの利点
def msort[T](less: (T, T) => Boolean)(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 (less(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(msort(less)(ys), msort(less)(zs))
}
}
カリー化された関数から部分適用を実施した例
scala> val intSort = msort((x: Int, y: Int) => x < y) _
intSort: (List[Int]) => List[Int] = <function>
scala> val reverseIntSort = msort((x: Int, y: Int) => x > y) _
reverseIntSort: (List[Int]) => List[Int] = <function>
16.7 Higher-order methods on class List
多くのリスト操作は同じような構造を持っている。
幾つかのパターンが何回も出てくる。
javaならforやwhileのidiomで書く
scalaならhigher-order operatorsを使ってもっと簡素に直接的に書ける。
Mapping over lists: map, flatMap and foreach
xs map f
リストの全ての要素にある関数を適用した結果をリスト化する。
val f = (x: T) => {...}: U
List[T](a, b, ...) map f equals List[U](f(a), f(b), ...)
scala> List(1, 2, 3) map (_ + 1)
res29: List[Int] = List(2, 3, 4)
xs flatMap f
map適用後のリストの要素(要素もリスト)を ::: で結合する。
scala> List.range(1, 5) flatMap (i => List.range(1, i) map (j => (i, j)))
res34: List[(Int, Int)] = List((2,1), (3,1), (3,2), (4,1), (4,2), (4,3))
上記はforでも同様に書ける。
for (i <- List.range(1, 5); j <- List.range(1, i)) yield (i, j)
xs foreach f
適用する関数も、foreach自体も値を返さないUnit型。
List(1, 2, 3, 4, 5) foreach (sum += _)
?? あまり関数型的ではない??
Filtering lists: filter, partition, find, takeWhile, dropWhile, and span
p は T => Boolean
xs filter p
xsの要素xのうちp(x) == trueのものだけ残す。
xs partition p equals (xs filter p, xs filter (!p(_)))
filterした要素のリストとfilterされた要素のリストを返す。
xs find p equals
(xs filter p) match {case Nil => None; case x :: xs => Some(x)}
filter結果が無ければNone, あればその先頭の要素のSome()を返す。
Option type
xs takeWhile p
先頭から連続してpを満たす要素のリスト。
scala> List(1, 2, 3, -4, 5) takeWhile (_ > 0)
res42: List[Int] = List(1, 2, 3)
xs dropWhile p
先頭から連続してpを満たす要素を取り除いたリスト。
scala> List(1, 2, 3, -4, 5) dropWhile (_ > 0)
res42: List[Int] = List(-4, 5)
xs span p equals (xs takeWhile p, xs dropWhile p)
先頭から連続してpを満たす要素のリストとその残りのリスト。
Predicates over lists: forall and exists
p は T => Boolean
xs forall p
xsの全ての要素がpを満たせばtrue
xs exists p
xsの要素のうち一つでもpを満たせばtrue
Folding lists: /: and :\
畳み込み(fold) ?? reduceとの差は??
foldLeft or /:
opは (U, T) => U
(z /: List(a, b, c)) (op) equals op(op(op(z, a), b), c)
foldRight or :\
opは (T, U) => U
(List(a, b, c) :\ z) (op) equals op(a, op(b, op(c, z)))
空リストList()に対してはzをそのまま返す。
/:, :\だと読み難いという場合のためにfoldLeft,foldRightの名前も定義あり。
foldLeft, foldRight自体の効率は同じだが、opにより異なる場合あり。
def flattenLeft[T](xss: List[List[T]]) = (List[T]() /: xss) (_ ::: _)
def flattenRight[T](xss: List[List[T]]) = (xss :\ List[T]()) (_ ::: _)
上記の場合は:::の性質からRightの方が効率が良い。
List[T]()の型指定はscalaでは必要。NilやList()ではNG
scalaの型推論の制限。Chapter 22
?? 再帰だと型推論が上手く出来ない?? 戻り値、引数の型が必須なのと同様??
?? 細かくvalに代入すると名前をつけるのが大変?? 短い名前でも良い??
Example: List reversal using fold
** foldや再帰を使うときの考え方の流れも説明しようとしている。
まず、foldLeftを使ったらどうなるかを考える。
def reverseLeft[T](xs: List[T]) = (startvalue /: xs)(operation)
このstartvalueとoperationを決められれば良い。
一番簡単な空リストxs = List()の反転がList()になるようにする。
置き換え(substitution)を使って実行結果を追っかける。
(startvalue /: List())(operation) // reverseLeftの定義から
== startvalue // /:の定義から
== List()
これでstartvalueはList()に決められる。
次に簡単な一要素のリストList(x)の反転がList(x)になるようにする。
(List() /: List(x))(operation) // reverseLeftの定義から
== operation(List(), x) // /:の定義から
== List(x) // 満たすべき結果から
== x :: List() // List(x)の別の表現
== {(ys, y) => y :: ys} (List(), x) // ここは思いつくかどうか?
これでoperationを{(ys, y) => y :: ys}に決められる。
これはconsの反対なのでsnocと呼ばれることがある。
soncがorder(1)なのでreverseLeftはorder(n)の計算量。
** 連立方程式を解くときや、検算をする時に似ている。
** なるべく簡単な制約条件を考えてそれを満たすようにすれば良い。
Sorting lists: sort
xs sort before ?? sortと言うmethodはない?? sortWithになった??
xsをbeforeの順にソートしたリストを返す。
before: (x: T, y: T) => Boolean
xがyより前に配置されるべき要素ならtrueとなるfunction
マージソートと同様のアルゴリズムを使っている。
class Listのmethodとして定義されている。
16.8 Methods of the List object
class Listのcompanion objectに定義されているoperation
factory methodsと特定の形式のリストに使うmethods
Creating lists from their elements: List.apply
List.apply(1, 2, 3) equals List(1, 2, 3)
Creating a range of numbers: List.range
List.range(from, until)
List.range(from, until, step)
scala> List.range(9, 1, -3)
res53: List[Int] = List(9, 6, 3)
fromは含む。untilは含まない。マイナス値でもOK。
Creating uniform lists: List.make
List.make(num, x)
scala> List.make(5, 'a')
res54: List[Char] = List(a, a, a, a, a)
要素xをnum個含むリスト。num == 0でも良い。
Unzipping lists: List.unzip
List.unzip(List((x1, y1), (x2, y2), ...))
equals (List(x1, x2), List(y1, y2), ...)
ペアになっているリストにしか適用できないのでインスタンスのmethodに出来ない。
scalaの型システムはインスタンスのmethodはその型なら全てに適用可能を要求。
?? 例外を投げれば良い気もするが、実行時に検知も出来ないと言う事??
Concatenating lists: List.flatten, List.concat
List.flatten(List(List((a, b), (c, d), ...))) equals List(a, b, c, d, ...)
List.concat(List((a, b), (c, d), ...)) equals List(a, b, c, d, ...)
concatは任意の数のリストを引数にとって結合する。
flattenはリストのリストを引数にとって結合する。
インスタンスのmethodに出来ないのはunzipと一緒。
Mapping and testing pairs of lists: List.map2, List.forall2, List.exists2
List.map2(List(a1, a2, ...), List(b1, b2, ...))(op: (a, b) => c)
equals List(op(a1, b1), op(a2, b2), ...)
List.forall2(List(a1, a2, ...), List(b1, b2, ...))(op: (a, b) => Boolean)
equals op(a1, b1) && op(a2, b2) && ...
List.exists2(List(a1, a2, ...), List(b1, b2, ...))(op: (a, b) => Boolean)
equals op(a1, b1) || op(a2, b2) || ...
二つのリストの各要素の対にopを適用した結果map, forall, exists相当。
16.9 Understanding Scala's type inference algorithm
scalaの型推論について
local, flow-based
MLやhaskell
global Hindley-Milner style
object-oriented subtypingと一緒に使う際はHindley-Milner styleより優れている。
制限はあるがコーナーケースで型annotationを追加すれば簡単に対応できる。
型annotation追加はデバッグの時も有用。
polymorphic methodsで分からない型エラーが出た場合。
自分の正しいと思う型annotationを追加すれば問題の原因を早くつかめる。
m(args)が適用された場合、最初にmethod mの型が確定しているかをチェックする。
val abcde = "abcde".toList
abcde sortWith (_ > _)
sortWithの型シグネチャは((T, T) => Boolean) => List[T]
適用するオブジェクトabcdeがList[Char]なのでAはCharで確定。
sortWithの型も確定。
パラメータ関数値は(Char, Char) => Boolean型に確定する。
msort(_ > _)(abcde)
msortの型シグネチャは((T, T) => Boolean)(List[T]) => List[T]
Tの型が分からないのでmsortの型は決まらない。
methodの型が決まらない場合は第一引数リストの型をチェックする。
第一引数リストの(_ > _)も型情報が無いので何も決まらない。ここで失敗。
** 第一引数の事ではないので注意！！ カリー化の時の最初の引数リスト
第二引数リスト以降は型推論に使わない。
?? 部分適用の際に省略されるかもしれないから??
回避策
型を指定する。
msort[Char](_ > _)(abcde), msort((_: Char) > (_: Char))(abcde)
第一引数リストにnon-function argumentsを持ってくる。
def msortSwapped[T](xs: List[T])(op: (T, T) => Boolean): List[T] = ...
カリー化する際には第一引数リストにnon-function argumentsを持って来た方が良い
(xss :\ List()) (_ ::: _) の場合
:\の型シグネチャは (B)((A, B) => B) => B
Bはxssの入力値からList[T]に確定したとする。List()はList[Nothing]。
第二引数リストの型が(List[T], List[Nothing]) => List[Nothing]
(_ ::: _)の型と一致しないのでエラーになる。
?? Catch-22 situation 何の事 ??
これを防ぐために List[Char]() 等とBの型を指定する必要がある。
?? List[Nothing]は任意のList[T]とマッチするからエラーにしなくても良い?
?? エラーにしないと型が分からないから実行できなくなる?
16.10 Conclusion
basic, first-orde, higher-order operations, utility methods, type inference
Listはscalaでは非常に良く使うので、詳しく使い方を知っている必要ある。
Listを含むcollectionについては次章。
0 件のコメント:
コメントを投稿