Scala School意訳(Collections)

http://twitter.github.com/scala_school/collections.html

以下は私の方でtypoや表示崩れを直したものです。

https://github.com/seratch/scala_school/blob/master/web/_posts/2011-05-03-lesson.textile

誤訳などありましたら、お手数ですが、ご指摘いただければ幸いです。

事前知識

Scalaの標準ライブラリのドキュメントは以下のURLで参照できます。
http://www.scala-lang.org/api/current/index.html

Martin Oderskyさんによるこちらの文書が大変参考になります。
http://www.scala-lang.org/docu/files/collections-api/collections.html
http://eed3si9n.github.com/scala-collections-doc-ja/

ScalaのコレクションAPIは「scala.collection.immutable._」「scala.collection.mutable._」の二つがあり、基本的には前者を指します。

Lists

val numbers = List(1, 2, 3, 4)
numbers: List[Int] = List(1, 2, 3, 4)

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List$

（訳者追記）
型パラメータの[Int]は推論されるので省略できますが、明示しても構いません。

val numbers = List[Int](1, 2, 3, 4)

Sets

Setには重複する要素がありません。

scala> Set(1, 1, 2)
res0: scala.collection.immutable.Set[Int] = Set(1, 2)

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.Set
http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.Set$

Tuple

タプルはクラスを定義せずに値をひとまとまりするのに使われます。

scala> val hostPort = ("localhost", 80)
hostPort: (String, Int) = (localhost, 80)

ケースクラスのような名前をつけられたアクセサはありません。
その代わりに位置によって命名されたアクセサがあります。それは0からではなく1から始まります。

scala> hostPort._1
res0: String = localhost

scala> hostPort._2
res1: Int = 80

タプルはパターンマッチによく合います。

hostPort match {
  case ("localhost", port) => ...
  case (host, port) => ...
}

タプルにはシンプルに2つの値でタプルをつくるための「->」というスパイスもあります。

scala> 1 -> 2
res0: (Int, Int) = (1,2)

http://www.scala-lang.org/api/current/index.html#scala.Tuple1
http://www.scala-lang.org/api/current/index.html#scala.Tuple2
http://www.scala-lang.org/api/current/index.html#scala.Tuple3
Tuple1からTuple22まであります。
http://www.scala-lang.org/api/current/index.html#scala.Tuple22

http://ja.wikipedia.org/wiki/%E3%82%BF%E3%83%97%E3%83%AB

Maps

Mapは基本的なデータタイプを保持することができます。

Map(1 -> 2)
Map("foo" -> "bar")

これは特殊な構文にみえますが「->」でタプルの生成ができるということを思い出してください。

Map()はレッスン#1（Basics）で学んだ引数をとる構文を使うこともできます。
Map(1 -> "one", 2 -> "two")は一つ目の要素はMapのキーとして、二つ目の要素はMapの値としてMap((1, "one"), (2, "two"))のように展開されます。

Mapの中にMapを保持したり、関数を値として保持することもできます。

Map(1 -> Map("foo" -> "bar"))
Map("timesTwo" -> timesTwo(_))

http://www.scala-lang.org/api/current/index.html#scala.collection.Map
http://www.scala-lang.org/api/current/index.html#scala.collection.Map$

Option

Optionは何かを保持したりしなかったりするコンテナです。
Optionの基本的なインタフェースはこのようになります。

trait Option[T] { 
  def isDefined: Boolean 
  def get: T 
  def getOrElse(t: T): T 
}

Option自体は汎用なインタフェースで、Some[T]とNoneという二つのサブクラスを持っています。
それではどのようにOptionが使われるか例を見てみましょう。

Map.getは戻り値としてOption型を返します。
Optionはメソッドがあなたが求める値を返すことができないかもしれないので、それに対して準備する必要があるということを知らせます。

scala> val numbers = Map(1 -> "one", 2 -> "two")
numbers: scala.collection.immutable.Map[Int,String] = Map((1,one), (2,two))

scala> numbers.get(2)
res0: Option[java.lang.String] = Some(two)

scala> numbers.get(3)
res1: Option[java.lang.String] = None

さあ、私達のデータはOption型の中に閉じ込められてしまったようです。これをどのように扱えばよいのでしょうか？

本能的に最初に思いつくのはisDefinedメソッドを使った条件式によるやり方かもしれません。

// 返された数を2で掛け算した結果、もしくは0を返したい
 val result = if (res1.isDefined()) { res1.get * 2 } else { 0 }

しかし、getOrElseかパターンマッチで処理することをおすすめします。
getOrElseは簡単にデフォルト値を定義することができます。

val result = res1.getOrElse(0) * 2

パターンマッチとOption型に自然な形で組み合わせることができます。

val result = res1 match { 
  case Some(n) => n * 2 
  case None => 0 
}

（訳者追記）
Option#getというメソッドもあって、手軽に値を取り出せますが

scala> val o = Some(1)
o: Some[Int] = Some(1)

scala> o.get
res3: Int = 1

Noneだった場合に実行時例外になってしまうので、getの使用はそのOptionがNoneでないことが自明な場合のみに控えた方がよいと思います。

scala> val o = None
o: None.type = None

scala> o.get
java.util.NoSuchElementException: None.get
	at scala.None$.get(Option.scala:274)
	at .<init>(<console>:10)

Scala Schoolにもあるように、OptionはパターンマッチやgetOrElseなどで処理します。

より応用的な内容はこちらの記事が参考になります。

http://kaitenn.blogspot.com/2011/03/scala-option-cheat-sheet.html

Functional Combinators

コンビネータ（結合子）がそう呼ばれるのは、それが結合されるからです。ある関数の出力はしばしば他の関数の入力となりえます。
最も多い用途は標準的なデータ構造に対する処理です。

map

リストの各要素に対してある関数を評価して同じ個数の要素を持ったリストを返します。

scala> numbers.map((i: Int) => i * 2)
res0: List[Int] = List(2, 4, 6, 8)

もしくは（定義によって）部分的に評価された関数に各要素を渡します。

scala> def timesTwo(i: Int): Int = i * 2
timesTwo: (i: Int)Int

scala> numbers.map(timesTwo _)
res0: List[Int] = List(2, 4, 6, 8)

（訳者追記）

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
からの引用です。

def map [B] (f: (A) ⇒ B): List[B]
  B: the element type of the returned collection.
  f: the function to apply to each element. 
  returns: a new collection of type That resulting from applying the given function f to each element of this list and collecting the results.

[use case] Builds a new collection by applying a function to all elements of this list.

foreach

foreachはmapに似ていますが結果を何も返しません。foreachは副作用だけを意図しています。

scala> numbers.foreach((i: Int) => i * 2)
returns nothing.

結果を保存しようとすることはできますが、それはUnit型（voidのようなもの）になります。

scala> val doubled = numbers.foreach((i: Int) => i * 2)
doubled: Unit = ()

（訳者追記）

Unitはvoidのようなものですが、厳密には空のタプルです。

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
からの引用です。

def foreach (f: (A) ⇒ Unit): Unit
def foreach [B] (f: (A) ⇒ B): Unit
  f: the function that is applied for its side-effect to every element. The result of function f is discarded.

[use case] Applies a function f to all elements of this list.

filter

渡された要素のうち、falseと評価されたものを取り除きます。Boolean型を返す関数をよく述語関数と呼びます。

scala> numbers.filter((i: Int) => i % 2 == 0)
res0: List[Int] = List(2, 4)
scala> def isEven(i: Int): Boolean = i % 2 == 0
isEven: (i: Int)Boolean

scala> numbers.filter(isEven _)
res2: List[Int] = List(2, 4)

（訳者追記）

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
からの引用です。

def filter (p: (A) ⇒ Boolean): List[A]
  p: the predicate used to test elements.
  returns: a new list consisting of all elements of this list that satisfy the given predicate p. The order of the elements is preserved.

Selects all elements of this list which satisfy a predicate.

zip

zipは二つのリストの中身を各要素がペアになっている一つのリストに統合します。

scala> List(1, 2, 3).zip(List("a", "b", "c"))
res0: List[(Int, String)] = List((1,a), (2,b), (3,c))

（訳者追記）

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
からの引用です。

def zip [B] (that: GenIterable[B]): List[(A, B)]
  B: the type of the second half of the returned pairs
  that: The iterable providing the second half of each result pair
  returns: a new collection of type That containing pairs consisting of corresponding elements of this list and that. The length of the returned collection is the minimum of the lengths of this list and that.

[use case]
Returns a list formed from this list and another iterable collection by combining corresponding elements in pairs. If one of the two collections is longer than the other, its remaining elements are ignored.

partition

partitionは述語関数に一致するかどうかに基いてリストを分割します。

scala> val numbers = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
numbers: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10).partition((i: Int) => i > 5)
res0: (List[Int], List[Int]) = (List(6, 7, 8, 9, 10),List(1, 2, 3, 4, 5)

（訳者追記）

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
からの引用です。

def partition (p: (A) ⇒ Boolean): (List[A], List[A])
  p: the predicate on which to partition.
  returns: a pair of lists: the first list consists of all elements that satisfy the predicate p and the second list consists of all elements that don't. The relative order of the elements in the resulting lists is the same as in the original list.

Partitions this list in two lists according to a predicate.

find

findはコレクションの中で述語関数にマッチした最初の要素を返します。

scala> List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10).find((i: Int) => i > 5)
res0: Option[Int] = Some(6)

（訳者追記）

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
からの引用です。

def find (p: (A) ⇒ Boolean): Option[A]
  p: the predicate used to test elements.
  returns: an option value containing the first element in the list that satisfies p, or None if none exists.

Finds the first element of the list satisfying a predicate, if any.

drop & dropWhile

dropは最初のi個の要素を落とします（取り除きます）。

scala> List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10).drop(5)
res0: List[Int] = List(6, 7, 8, 9, 10)

dropWhileは述語関数にマッチしない要素を取り除きます。これは（dropWhileを使った）dropの再実装です。

scala> List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10).dropWhile((i: Int) => i < 6)
res0: List[Int] = List(6, 7, 8, 9, 10)

（訳者追記）

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
からの引用です。

def drop (n: Int): List[A]
  n: the number of elements to drop from this list.
  returns: a list consisting of all elements of this list except the first n ones, or else the empty list, if this list has less than n elements.

Selects all elements except first n ones.

def dropWhile (p: (A) ⇒ Boolean): List[A]
  p: The predicate used to test elements.
  returns: the longest suffix of this list whose first element does not satisfy the predicate p.

Drops longest prefix of elements that satisfy a predicate.

foldLeft

scala> val numbers = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
numbers: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> numbers.foldLeft(0)((m: Int, n: Int) => m + n)
res0: Int = 55

0は最初の値です（numbersはList[Int]型であることを思い出してください）。
そしてmはアキュムレータとしてふるまいます。

視覚的にみてみましょう：

scala> List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10).foldLeft(0) { (m: Int, n: Int) => println("m: " + m + " n: " + n); m + n }
m: 0 n: 1
m: 1 n: 2
m: 3 n: 3
m: 6 n: 4
m: 10 n: 5
m: 15 n: 6
m: 21 n: 7
m: 28 n: 8
m: 36 n: 9
m: 45 n: 10
res0: Int = 55

（訳者追記）

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
からの引用です。

def foldLeft [B] (z: B)(f: (B, A) ⇒ B): B
  B: the result type of the binary operator.
  z: the start value.
  returns: the result of inserting op between consecutive elements of this list, going left to right with the start value z on the left:
    op(...op(z, x,,1,,), x,,2,,, ..., x,,n,,)
    where x,,1,,, ..., x,,n,, are the elements of this list.

Applies a binary operator to a start value and all elements of this list, going left to right.

アキュムレータについてはこちらを。
アキュムレータ - Wikipedia

foldRight

リストの逆方向から実行されることを除いてfoldLeftと同じです。

scala> val numbers = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
numbers: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> numbers.foldRight(0) { (m: Int, n: Int) => println("m: " + m + " n: " + n); m + n }
m: 10 n: 0
m: 9 n: 10
m: 8 n: 19
m: 7 n: 27
m: 6 n: 34
m: 5 n: 40
m: 4 n: 45
m: 3 n: 49
m: 2 n: 52
m: 1 n: 54
res0: Int = 55

（訳者追記）

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
からの引用です。

def foldRight [B] (z: B)(f: (A, B) ⇒ B): B
  B: the result type of the binary operator.
  z: the start value.
  returns: the result of inserting op between consecutive elements of this list, going right to left with the start value z on the right:
    op(x,,1,,, op(x,,2,,, ... op(x,,n,,, z)...))
    where x,,1,,, ..., x,,n,, are the elements of this list.

Applies a binary operator to all elements of this list and a start value, going right to left.

flatten

flatternは入れ子になったデータ構造の階層を一つ崩します。

scala> List(List(1, 2), List(3, 4)).flatten
res0: List[Int] = List(1, 2, 3, 4)

（訳者追記）

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
からの引用です。

def flatten [B] : List[B]
  B: the type of the elements of each traversable collection.
  returns: a new list resulting from concatenating all element lists.

[use case]
Converts this list of traversable collections into a list in which all element collections are concatenated.

flatMap

flatMapはよく使われるコンビネータ（結合子）で、mapとflattenを組み合わせたものです。
入れ子になったリストを処理する関数を引数に処理した結果を連結します。

scala> val nestedNumbers = List(List(1, 2), List(3, 4))
nestedNumbers: List[List[Int]] = List(List(1, 2), List(3, 4))

scala> nestedNumbers.flatMap(x => x.map(_ * 2))
res0: List[Int] = List(2, 4, 6, 8)

mapしてflattenする処理の省略形と考えてよいでしょう。

scala> nestedNumbers.map(x: List[Int] => x.map(_ * 2)).flatten
res1: List[Int] = List(2, 4, 6, 8)

このmapとflattenを呼んでいる例は、これまでにみてきた関数の性質である「結合子」のまさに具体例ですね。

（訳者追記）

http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List
からの引用です。

def flatMap [B] (f: (A) ⇒ GenTraversableOnce[B]): List[B]
  B: the element type of the returned collection.
  f: the function to apply to each element.
  returns: a new collection of type That resulting from applying the given collection-valued function f to each element of this list and concatenating the results.

[use case]
Builds a new collection by applying a function to all elements of this list and concatenating the results.

Generalized functional combinators

これまで私達はコレクションを扱う関数のグラブバッグ（小さなプレゼントがたくさん入った袋）を学んできました。
でも、関数のコンビネータ（結合子）を自分で書けるようになりたいですよね。

興味深いことに、これまでに出てきた全ての関数の例はfold関数の上に書くことができるものです。
では実際に例を見てみましょう。

def ourMap(numbers: List[Int], fn: Int => Int): List[Int] = {
  numbers.foldRight(List[Int]()) { (x: Int, xs: List[Int]) =>
    fn(x) :: xs
  }
}

scala> ourMap(numbers, timesTwo(_))
res0: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

なぜfoldRightの引数に「List[Int]()」と書かなければいけないのでしょうか？
さすがにScalaもあなたがIntの空リストに値を蓄積していきたいかどうかを認識するほどには賢くなかったのです。

Map?

これまで見てきた全ての関数コンビネータ（結合子）はMap型にも作用します。
MapはペアのListと考える事ができるので、関数はキーと値のペアに対して処理します。

scala> val extensions = Map("steve" -> 100, "bob" -> 101, "joe" -> 201)
extensions: scala.collection.immutable.Map[String,Int] = Map((steve,100), (bob,101), (joe,201))

電話番号が200より小さいエントリをフィルターしてみましょう。

scala> extensions.filter((namePhone: (String, Int)) => namePhone._2 < 200)
res0: scala.collection.immutable.Map[String,Int] = Map((steve,100), (bob,101))

タプルが与えられるので、位置のアクセサでキーと値を取り出さなければいけません。ゲッ（最悪だ）！

しかし、ラッキーでした。
私達はパターンマッチを使ってキーと値をいい感じに取り出すことができるのです。

scala> extensions.filter(case (name, extension) => extension < 200)
res0: scala.collection.immutable.Map[String,Int] = Map((steve,100), (bob,101))

なぜこれが動作するのでしょうか？
なぜ部分的なパターンマッチに値を渡すことができるのでしょうか？

それでは、次週をお楽しみに！