Scala School意訳(More collections)

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

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

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

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

The basics

List

スタンダードな単方向リスト(Singly linked list)です。

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

関数型言語であれば期待する通り、consでリストに付け加えることができます。

scala> 1 :: 2 :: 3 :: Nil
res1: List[Int] = List(1, 2, 3)

Seq

Seqは順序を持ったコレクションです。

scala> Seq(1, 1, 2)
res3: Seq[Int] = List(1, 1, 2)

Map

Mapはキーと値のコンテナです。

scala> Map('a' -> 1, 'b' -> 2)

res4: scala.collection.immutable.Map[Char,Int] = Map((a,1), (b,2))

The Hierarchy

これらは全てtraitです。mutableパッケージとimmutableパッケージは、これらのtraitに対してそれぞれ独自の実装を持っています。

Traversable

全てのコレクションはその要素を巡回することができます。このtraitは、もしあなたがforeachを実装すればforeachの単位として書かれたコンビネータを提供します。

（訳者追記）
これはforeachだけが「Abstract Value Members」にあることを言っています。

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

Iterable

要素のイテレータを返すiterator()というメソッドを持っています。

Seq

順序を持った要素の並びです。

Set

重複した要素を持たないコレクションです。

Map

キーと値のペアの集まりです。

The methods

Traversable

以下にある全てのメソッドはずっと下まで有効です。引数や戻り値の型は常に同じではなく、サブクラスは自由にoverrideすることができます。

def head : A
def tail : Traversable[A]

ここに関数のコンビネータが定義されています。

def map [B] (f: (A) => B) : CC[B]

各要素を関数fで変換したコレクションを返します。

def foreach[U](f: Elem => U): Unit

各要素に対して関数fを実行してコレクションに変化を起こします。

def find (p: (A) => Boolean) : Option[A]

述語関数（predicate function）にマッチする最初の要素を返します。

def filter (p: (A) => Boolean) : Traversable[A]

述語関数にマッチする全ての要素を返します。


Partitioning:

def partition (p: (A) ⇒ Boolean) : (Traversable[A], Traversable[A])

コレクションを述語関数に基いて二つに分割します。

def groupBy [K] (f: (A) => K) : Map[K, Traversable[A]]


Conversion:

興味深いことに、あるコレクション型を別の型に変換することができます。

def toArray : Array[A]
def toArray [B >: A] (implicit arg0: ClassManifest[B]) : Array[B]
def toBuffer [B >: A] : Buffer[B]
def toIndexedSeq [B >: A] : IndexedSeq[B]
def toIterable : Iterable[A]
def toIterator : Iterator[A]
def toList : List[A]
def toMap [T, U] (implicit ev: <:<[A, (T, U)]) : Map[T, U]
def toSeq : Seq[A]
def toSet [B >: A] : Set[B]
def toStream : Stream[A]
def toString () : String
def toTraversable : Traversable[A]

MapをArrayに変換してみましょう。キーと値のペアの配列が得られます。

scala> Map(1 -> 2).toArray
res41: Array[(Int, Int)] = Array((1,2))

Iterable

イテレータへのアクセスが追加されます。

def iterator: Iterator[A]

イテレータによって何がもたらされるのでしょうか？

def hasNext(): Boolean
def next(): A

これは非常にJava風なインタフェースです。
きっとScalaではイテレータを使っているのを見かけることはあまりないでしょう。
おそらく関数のコンビネータやfor式を多く見ることになるでしょう。

Set

def contains(key: A): Boolean
def +(elem: A): Set[A]
def -(elem: A): Set[A]

Map

キーによる探索つきのキーと値のペアのシーケンスです。

このようにペアのリストをapply()メソッドに渡すか

scala> Map("a" -> 1, "b" -> 2)
res0: scala.collection.immutable.Map[java.lang.String,Int] = Map((a,1), (b,2))

あるいはこのようにします。

scala> Map(("a", 2), ("b", 2))
res0: scala.collection.immutable.Map[java.lang.String,Int] = Map((a,2), (b,2))

余談ですが

「->」は一体何でしょう？これは特別な構文という分けではありません。タプル（ペア）を返すメソッドなのです。

scala> "a" -> 2
res0: (java.lang.String, Int) = (a,2)

忘れないでください。これは以下の記述のただのシンタックスシュガーです。

scala> "a".->(2)
res1: (java.lang.String, Int) = (a,2)

また「++」を使ってMapを構築する事もできます。

scala> Map.empty ++ List(("a", 1), ("b", 2), ("c", 3))
res0: scala.collection.immutable.Map[java.lang.String,Int] = Map((a,1), (b,2), (c,3))

Commonly used subclasses

HashSet and HashMap

高速な探索が可能で、これらのコレクションの最も一般的な形態です。

TreeMap

これはSortedMapのサブクラスです。順序づけられたアクセスが可能です。

Vector

ランダムアクセスと更新が高速です。

scala> IndexedSeq(1, 2, 3)
res0: IndexedSeq[Int] = Vector(1, 2, 3)

（訳者追記）
IndexedSeqのデフォルトの実装がVectorです。

Range

一定の間隔で順序付けられたInt型のシーケンスです。
これまではカウントつきのforループで使われていたような場所でこれをよく見かけるでしょう。

scala> for (i <- 1 to 10) { println(i) }
1
2
3
4
5
6
7
8
9
10

Rangeは普通の関数で使えるようなコンビネータを持っています。

scala> (1 to 10).map { i => i }
res0: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

Defaults

これらのtraitはそれぞれ（コンパニオンオブジェクトに定義された）applyメソッドを使うとデフォルトの実装でインスタンスを得ることができます。
例えば、Iterable(1,2)はデフォルトの実装としてList型を返します。

scala> Iterable(1, 2)
res0: Iterable[Int] = List(1, 2)

Seqでも同様です。

scala> Seq(1, 2)
res3: Seq[Int] = List(1, 2)

scala> Iterable(1, 2)
res1: Iterable[Int] = List(1, 2)

scala> Sequence(1, 2)
warning: there were deprecation warnings; re-run with -deprecation for details
res2: Seq[Int] = List(1, 2)

Setはこのようになります。

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

（訳者追記）

一箇所warningでていますが「scala -deprecation」で起動してみると「Sequenceはもう使うな、Seqを使え」ということですね。

scala> Sequence(1,2)
<console>:8: warning: value Sequence is deprecated: use Seq instead
       Sequence(1,2)
       ^
res0: Seq[Int] = List(1, 2)

scala> Seq(1,2)
res1: Seq[Int] = List(1, 2)

IndexedSeq

要素へのランダムアクセスと長さの取得が高速です。

LinearSeq

headメソッドによる最初の要素へのアクセスが高速です。tailメソッドによる処理（最初の要素を除いた2番目以降の要素全件の取得）も高速です。

Mutable vs. Immutable

immutableに対する・・

賛成意見：マルチスレッドでの変更ができない

反対意見：一切変更できない

Scalaは私たちに実利的であることも許しています。
immutableを推奨していますが、mutableなものを必要とすることを罰したりはしません。
これは「var」対「val」と似たような話です。
私たちは常にvalから始めてもし必要になったらvarに戻すのです。

私たちはimmutableなバージョンのコレクションから始めることを好みます。もしそれがパフォーマンスに影響するならmutableに変更しますが。
immutableなコレクションを使うということは、マルチスレッドでの意図しない共有オブジェクトの変更が起きないということを意味します。

Mutable

これまで話に出てきた全てのクラスはimmutableでした。
では、一般的によく使われるmutableなコレクションについて話しましょう。

HashMap

getOrElseUpdate、+=といったメソッドがあります。

scala> val numbers = collection.mutable.Map(1 -> 2)
numbers: scala.collection.mutable.Map[Int,Int] = Map((1,2))

scala> numbers.get(1)
res0: Option[Int] = Some(2)

scala> numbers.getOrElseUpdate(2, 3)
res54: Int = 3

scala> numbers
res55: scala.collection.mutable.Map[Int,Int] = Map((2,3), (1,2))

scala> numbers += (4 -> 1)
res56: numbers.type = Map((2,3), (4,1), (1,2))

ListBuffer and ArrayBuffer

（訳者追記）
見出しだけで特に何も書いていなかったので少し利用例を貼り付けてみました。

http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.ListBuffer

scala> import collection.mutable.ListBuffer
import collection.mutable.ListBuffer

scala> val lbuf = new ListBuffer[String]
lbuf: scala.collection.mutable.ListBuffer[String] = ListBuffer()

scala> lbuf.append("a","b","c")

scala> lbuf
res1: scala.collection.mutable.ListBuffer[String] = ListBuffer(a, b, c)

scala> lbuf.appendAll(List("d","e","f"))

scala> lbuf
res4: scala.collection.mutable.ListBuffer[String] = ListBuffer(a, b, c, d, e, f)

scala> val newOne: ListBuffer[String] = lbuf ++ List("g")
newOne: scala.collection.mutable.ListBuffer[String] = ListBuffer(a, b, c, d, e, f, g)

scala> lbuf += "g"
res7: lbuf.type = ListBuffer(a, b, c, d, e, f, g)

scala> lbuf ++= List("h")
res9: lbuf.type = ListBuffer(a, b, c, d, e, f, g, h)

scala> lbuf -= "h"
res10: lbuf.type = ListBuffer(a, b, c, d, e, f, g)

scala> lbuf --= List("f","g")
res11: lbuf.type = ListBuffer(a, b, c, d, e)

scala> lbuf --= List("f","g")
res12: lbuf.type = ListBuffer(a, b, c, d, e)

scala> lbuf foreach println
a
b
c
d
e

scala> lbuf filter ( _ != "b" )
res14: scala.collection.mutable.ListBuffer[String] = ListBuffer(a, c, d, e)

ArrayBufferとの違いを確認してみましょう。

http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.ArrayBuffer

LinkedList and DoublyLinkedList

（訳者追記）
見出しだけで特に何も書いていなかったので少し利用例を貼り付けてみました。

http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.LinkedList
http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.DoubleLinkedList

前者がSingly linked listで後者がDoubly linked listの実装になっています。

import collection.mutable.LinkedList
val l = LinkedList(1,2,3)
l head // 1
l tail // LinkedList(2, 3)
l foreach print(e => print(e + " "))
// 1 2 3
val ll = l ++ List(1,2,3)
val ll = l ++ LinkedList(1,2,3)
l foreach print(e => print(e + " "))
// 1 2 3
ll foreach print(e => print(e + " "))
// 1 2 3 4 5 6

import collection.mutable.DoubleLinkedList
val l = DoubleLinkedList(1,2,3)
val ll = l ++ List(4,5,6)
l head // 1
l tail // DoubleLinkedList(2, 3)
l foreach print(e => print(e + " "))
// 1 2 3
ll foreach print(e => print(e + " "))
// 1 2 3 4 5 6

PriorityQueue

（訳者追記）
見出しだけで特に何も書いていなかったので少し利用例を貼り付けてみました。

http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.PriorityQueue

import collection.mutable.PriorityQueue
val pq = PriorityQueue[Int]()
pq.enqueue(1)
pq.enqueue(5)
pq.enqueue(2)
pq.enqueue(3)
pq.enqueue(4)
pq.enqueue(2)
pq.enqueue(2)
pq.enqueue(3)
pq.enqueue(3)

scala> pq
res73: scala.collection.mutable.PriorityQueue[Int] = PriorityQueue(5, 4, 2, 3, 3, 2, 2, 1, 3)

pq.dequeue // 5
pq.dequeue // 4
pq.dequeue // 3
pq.dequeue // 3
pq.dequeue // 3
pq.dequeue // 2
pq.dequeue // 2
pq.dequeue // 2
pq.dequeue // 1
pq.isEmpty // true
pq.dequeue // java.util.NoSuchElementException:

PriorityQueueのコンストラクタは暗黙のパラメータでOrdering[T]を受け取っているので、差し替えて優先度のつけ方を変えることができます。

val pq = new PriorityQueue[Int]()(new Ordering[Int] { def compare(x: Int, y: Int) = if(x < y) 1 else -1 })
pq.enqueue(2)
pq.enqueue(1)
pq.enqueue(3)
pq.dequeue // 1
pq.dequeue // 2
pq.dequeue // 3

Stack and ArrayStack

（訳者追記）
見出しだけで特に何も書いていなかったので少し利用例を貼り付けてみました。

http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.Stack
http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.ArrayStack

import collection.mutable.Stack
val stack = new Stack[Int]

stack.push(1)
stack.push(2)
stack.push(3)

stack.pop // 3
stack.pop // 2
stack.pop // 1
stack.isEmpty // true
stack.pop // java.util.NoSuchElementException: head of empty list

import collection.mutable.ArrayStack
val stack = new ArrayStack[Int]

StringBuilder

興味深いことにStringBUilderもコレクションなのです。

（訳者追記）

scala> val sb = new collection.mutable.StringBuilder
sb: StringBuilder =

scala> sb.append("sss").append("ttt")
res15: StringBuilder = sssttt

scala> sb foreach println
s
s
s
t
t
t

Life with Java

JavaConversionsパッケージに定義されている暗黙の型変換を使えば、簡単にJavaとScalaのコレクション型を行き来することができます。

import scala.collection.JavaConversions._
val sl = new scala.collection.mutable.ListBuffer[Int]
val jl : java.util.List[Int] = sl
val sl2 : scala.collection.mutable.Buffer[Int] = jl
assert(sl eq sl2)

双方向の変換があります。

scala.collection.Iterable <=> java.lang.Iterable
scala.collection.Iterable <=> java.util.Collection
scala.collection.Iterator <=> java.util.{ Iterator, Enumeration }
scala.collection.mutable.Buffer <=> java.util.List
scala.collection.mutable.Set <=> java.util.Set
scala.collection.mutable.Map <=> java.util.{ Map, Dictionary }
scala.collection.mutable.ConcurrentMap <=> java.util.concurrent.ConcurrentMap

さらに、以下のような一方向な変換も提供されています。

scala.collection.Seq => java.util.List
scala.collection.mutable.Seq => java.util.List
scala.collection.Set => java.util.Set
scala.collection.Map => java.util.Map