Scalaのコレクション入門

入門記事の一覧

About - case class HatenaDiary(id: Symbol = ’seratch2)

Scalaのバージョン

この記事が対象とするScalaのバージョンは「2.9.0.final」です。

1 to 3?

まずこの記事の中でよく出てくる「1 to 3」のような構文について説明します。

これは1という Int 型の to(Int) というメソッド呼び出しで見た目通りに「1,2,3」のコレクションを返します。

val oneToThree = 1.to(3)
// Range(1, 2, 3)

その他に until もこの記事では時々出てきます。

val oneUntilThree = 1.until(3)
// Range(1, 2)

数字の並びを出力したい

ループ処理を書く

Scala でも while ループや do-while ループを書く事はできます。

var i = 0
while (i < 5 ) {
  println(i)    
  i += 1
}
// 0 1 2 3 4

普通、同じ処理を書くなら以下のようにします。

for 式を使う

for( i <- 0 until 5 ) println(i)
// 0 1 2 3 4

コレクション型に生えている foreach メソッドを使う

(0 until 5) foreach { (i) => println(i) }
// 0 1 2 3 4

mutable? immutable?

Scala で List や Map というと普通は immutable なコレクションを指します。

val list = List(1,2,3,4) // 型パラメータをつけるとList[Int](1,2,3)になるが推論可能
val map = Map("a" -> "aa", "b" -> "bb") // Map[String,String]()

どうしても mutable な List や Map が必要な場合は scala.collection.mutable にある ListBuffer や HashMap を使います。

val listBuffer = new collection.mutable.ListBuffer[String]
listBuffer.append("aaa")
val mutableMap = new collection.mutable.HashMap[String,String]
mutableMap.update("aa","bbb")

for 式（内包表記）

「i <- 1 to 3」の構文の事をジェネレータ（generator）と呼びます。

for(i <- 1 to 3 ) println(i) 
// 1 2 3

i を受け取った処理をブロックにすることができます。

for(i <- 1 to 3 ) {
  i match {
    case 1 => println("One")
    case 2 => println("Two")
    case 3 => println("Three")
    case _ => println("Unknown")
  }
} 
// One Two Three

yield で返した値の集合を新しいコレクションとして返します。

val newList = for(i <- 1 to 3) yield i
// Vector(1, 2, 3)

def zeroTo(max:Int) = { for(i <- 0 to max) yield i }
val zeroToFive = zeroTo(5)
// Vector(0, 1, 2, 3, 4, 5)

yield に渡す値で処理を呼び出す事ができます。また yield の後にブロックを記述することもできます。

val squares = for(i <- 0 to 3 ) yield i * i
// Vector(0, 1, 4, 9)
def square(i: Int) = i * i
val squares = for(i <- 0 to 3 ) yield square(i)
// Vector(0, 1, 4, 9)

val newList= for(i <- 1 to 10) yield { 
  if ( i < 4 ) 0 else i 
} 
// Vector(0, 0, 0, 4, 5, 6, 7, 8, 9, 10)

以下のように yield をブロックの中に含める事はできません。コンパイルエラーになります。

val newList= for(i <- 1 to 10) {
  if ( i < 4 ) yield 0
  else yield i
}
// error: illegal start of simple expression

続いて if で続けるフィルターを定義して使ってみます。

for(i <- 1 to 10 if i > 8 ) println(i) 
// 9 10

for(i <- 1 to 10
  if i > 3
  if i % 2 == 0
) println(i) 
// 4 6 8 10

複数のジェネレータを同時に使う事もできます。

for(
  i <- 1 to 2;
  j <- 3 to 5;
  k <- 6 to 7
) print("[" + i + "," + j + "," + k + "]")
// [1,3,6][1,3,7][1,4,6][1,4,7][1,5,6][1,5,7][2,3,6][2,3,7][2,4,6][2,4,7][2,5,6][2,5,7]

ジェネレータの計算結果を他のジェネレータから参照する事もできます。

for(
  i <- 1 to 2;
  j = i * 2
) print("[" + i + "," + j + "]")
// [1,2][2,4]
for(
  i <- 1 to 2;
  j <- (3 * i to 5 * i)
) print("[" + i + "," + j + "]")
// [1,3][1,4][1,5][2,6][2,7][2,8][2,9][2,10]

具体的に for 式は何をやっているか

こちらのページが参考になります。

http://www.ne.jp/asahi/hishidama/home/tech/scala/collection/for.html

蛇足ですが、こちらにも例をあげておきます。

まず yield なしの場合は foreach と同じように変換されます。

for (i <- List(1,2,3)) println(i)

↓

List(1,2,3) foreach { i => println(i) }

ジェネレータが二つになると foreach がネストします。

for { 
  i <- List(1,2,3)
  j <- List(2,3,4)
} println(i + j)

↓

List(1,2,3) foreach {
  i => List(2,3,4) foreach {
    j => println(i + j)
  }
}

「=」による代入を組み合わせている場合は以下のように map で要素のタプルを作ってから foreach で処理します。

for { 
  i <- List(1,2,3)
  j = i * 2
} println(i + j)

↓

List(1,2,3) map { 
  i => (i, i * 2) 
} foreach { 
  case (i, j) => println(i + j) 
}

yield で値を返す場合は、一番内側は map、それ以外は flatMap に変換されます。
まず、ネストしていない場合はシンプルに map だけです。

for (i <- List(1,2,3)) yield i * 2

↓

List(1,2,3) map { i => i * 2 }

ネストしている場合は、一番内側が map でそれ以外は全て flatMap になります。

for { 
  i <- List(1,2,3)
  j <- List(2,3,4)
} yield i + j

↓

List(1,2,3) flatMap {
  i => List(2,3,4) map {
    j => i + j
  }
}

List#foreach の書き方

(0 until 5) foreach { (i) => println(i) }
// 0 1 2 3 4

引数が一つの場合はかっこを省略できます。

(0 until 5) foreach { i => println(i) }

この例では foreach メソッドに関数オブジェクトを渡しています。より丁寧に書くと以下のようになります。

(0 until 5).foreach((i:Int) => { println(i) })
// 0 1 2 3 4

また、いきなり引数に対するパターンマッチを書くこともできます。

これは foreach の引数に受け取る関数が Function1 なのでそのサブ型である PartialFunction も受け取れるためです。

List(0,1,2,3,4,"S") foreach {
  case i: Int => println(i)
  case _ => println("NaN")
}
// 0 1 2 3 4 NaN

コレクション型から新しいコレクションをつくる

foreach は戻り値が Unit の関数なので、その後の処理に値を渡す事はできません。

あるコレクションから対象を絞り込んだり、値を加工したものを返したい場合は map などを使います。

// 「_」はプレースホルダー、引数が入っています。filter { i => i >= 2 }でも同じです。
val newList = List(1,2,3,4) filter { _>=2 } 
// List(2, 3, 4)

Map 型のオブジェクトでは、このように key と value の組み合わせを引数として受け取ります。

val values = Map("aaa" -> "AAA", "bbb" -> "BBB") map { case (k,v) => v } 
// List(AAA, BBB)

cons（コンス）

「::」や「:::」のような記号が List 型ではしばしば用いられます。

これをcons（コンス）といいます。consはリストの連結や抽出子（Extractor）としての役割をこなすことができます。

val list1 = List(1, 2)
val list2 = List(3, 4, 5)
list1 :: list2  // => List(List(1, 2), 3, 4, 5)
list1 ::: list2 // =>  List(1, 2, 3, 4, 5)

抽出子についてはパターンマッチに関する入門記事もご参照下さい。

def printAll(chars: List[String]): Unit = { 
   chars match {
     case head :: Nil => println(head) 
     case head :: tail => {
       print(head)
       printAll(tail)
     }
     case _ =>
   }
}
printAll(List("H","e","l","l","o"))
// "Hello"

コレクションAPIを知る

ここから先は体系的にコレクション API を学ぶための導入です。

The Scala 2.8 Collections API

Martin Odersky氏によるコレクション API についてのドキュメントです。

http://www.scala-lang.org/docu/files/collections-api/collections.html

有志の方による日本語訳もあります。

http://www.tatapa.org/~takuo/scala_collections_2.8/collections.html

http://eed3si9n.github.com/scala-collections-doc-ja/

コレクション操作のボキャブラリ

Scala のコレクション API を使いこなすと、ほとんどのコレクションに関する問題を簡潔に解決する事ができます。

ここでは「scala.collection.immutable._」のAPIのみ扱います。

どの型にどんなAPIがあるのかを知る

List や Map は共に LinearSeq のサブ型なので LinearSeq で定義されている API はどちらも利用する事ができます。

また、実は String も Predef での暗黙の型変換により StringOps という IndexedSeq のサブ型に変換されるので IndexedSeq で定義される API は呼び出す事ができます。

この辺の階層関係については「The Scala 2.8 Collections API」にある以下の図で把握する事ができます。

ここから先は上記の図に出てくるそれぞれの型の API の簡単な呼び出し例を列挙していきます。

collection.immutable.Traversable

++/++:

List(1,2,3) ++ List(4) // List(1,2,3,4)
List(1,2,3) ++: List(4) // List(1,2,3,4)

head/headOption

先頭の要素を返します。

List(1,2,3).head // 1
List(1,2,3).headOption // Some(1)

tail

最初の要素以外のコレクションを返します。

List(1,2,3).tail // List(2,3)

init

最後の要素以外のコレクションをを返します。

List(1,2,3).init // List(1,2)

last/lastOption

最後の要素を返します。

List(1,2,3).last // 3
List(1,2,3).lastOption // Some(3)

foldLeft

渡された値を初期値としてコレクションの要素を左側から順に（＝先頭から）処理しながら計算をしていくことができます。

以下の例だと初期値5の sum をアキュムレータのようにして扱います。

val result = List(1,2,3,4).foldLeft(5){ (sum,i) => 
  println("sum:" + sum + ",i:" + i); sum*i 
}
// sum:5,i:1
// sum:5,i:2
// sum:10,i:3
// sum:30,i:4

// result は 120 に

以下の書き方でも同じです。

(5/:List(1,2,3,4)){ (sum,i) => sum*i } // 120

foldRight

foldLeft の逆です。コレクションの末尾から処理して最終的に計算結果の値を一つ返します。

List(1,2,3,4).foldRight(5){ (i,sum) => 
  println("i:" + i + ",sum:" + sum); i*sum 
} 
// i:4,sum:5
// i:3,sum:20
// i:2,sum:60
// i:1,sum:120

// result は 120 に

以下の書き方でも同じです。

(List(1,2,3,4):\5){ (i,sum) => i*sum } // 120

reduceLeft

一つ目の要素を foldLeft の第一引数に渡して実行するのと同じです。

val result = List(1,2,3,4).reduceLeft { (sum,i) => 
  println("sum:" + sum + ",i:" + i); sum*i 
}
// sum:1,i:2
// sum:2,i:3
// sum:6,i:4

// result は 24 に

reduceRight

一つ目の要素を foldRight の第一引数に渡して実行するのと同じです。

val result = List(1,2,3,4).reduceRight { (i,sum) => 
  println("i:" + i + ",sum:" + sum); sum*i 
}
// i:3,sum:4
// i:2,sum:12
// i:1,sum:24

// result は 24 に

foreach

戻り値なしですべての要素を処理します。

List("foo","bar","baz") foreach { print } 
// foobarbaz

List("foo","bar","baz") foreach { str => print(str) } 
// foobarbaz

filter

条件にマッチするものだけを抽出します。

List(1,2,3,4,5,6,7,8) filter ( i => i < 3 || i > 5 ) 
// List(1,2,6,7,8)

filterNot

条件にマッチしないものだけを抽出します。

List(1,2,3,4,5,6,7,8) filterNot ( i => i < 3 || i > 5 ) 
// List(3,4,5)

drop

List(1,2,3).drop(0) // List(1, 2, 3)
List(1,2,3).drop(1) // List(2, 3)
List(1,2,3).drop(2) // List(3)
List(1,2,3).drop(5) // List()

dropWhile

条件が true の間だけ、要素を取り除きます。以下の例だと 3 で条件が false になるので以降の要素は drop されません。

List(1,2,3,4,5,6,7,8) dropWhile( i => i < 3 || i > 5 ) 
// List(3,4,5,6,7,8)

take

List(1,2,3,4,5).take(2) // List(1,2)

takeWhile

dropWhile と同様です。条件が true の間だけ要素を take します。3 で条件が false になるので以降の要素は take されません。

List(1,2,3,4,5,6,7,8) takeWhile( i => i < 3 || i > 5 ) 
// List(1,2)

map

全要素を処理してつくった新しいコレクションを返します。

List(1,2,3) map ( i => (i, i*i) ) 
// List((1,1), (2,4), (3,9))

flatMap

map で処理すると入れ子になってしまうようなものは・・

list.map ( i => (1 to i) map { j => (i,j) }) 
// List(Vector((1,1)), Vector((2,1), (2,2)), Vector((3,1), (3,2), (3,3)))

flatMap では入れ子にならないコレクションとして返ります。

val list = List(1,2,3)
list flatMap ( i => (1 to i) map { j => (i,j) }) 
// List((1,1), (2,1), (2,2), (3,1), (3,2), (3,3))

flatten

入れ子になったコレクションをフラットにしたものを返します。

List(List(1,2),List(3)).flatten 
// List(1,2,3)

List(List(1,2),3).flatten 
// error: No implicit view available from Any => scala.collection.TraversableOnce[B].

collect

PartialFunction を使って新しいコレクションをつくります。

collectはPartialFunction#isDefinedAt(element) が true になる要素のみを処理した新しいコレクションを返します（filter した上で map している感じ）。

val pf : PartialFunction[Int,Int] = { case i if i > 1 => i * 2 }
List(1,2,3) collect(pf) // List(4,6)

以下のように書くことができます。

List(1,2,3) collect { case(i) if i > 1 => i * 2 } 
// List(4,6)

splitAt

指定されたn番目の要素を境に分割します（n番目は後者に含まれる）。

List(1,2,3,4,5).splitAt(2) 
// (List(1,2), List(3,4,5))

slice

List(1,2,3,4,5) slice (1,3) 
// List(2,3)

partition

条件を満たすものとそうでないものに分割したタプルを返します。

List(1,2,3,4,5) partition ( _ < 3 ) 
// (List(1, 2),List(3, 4, 5))

List(1,2,3,4,5) partition ( _ > 3 ) 
// (List(4, 5),List(1, 2, 3))

span

partition と似ていますが span は前から順にたどって条件を満たさないものを境界に分割します。

以下の一つ目の例のようにいきなり一つ目から条件を満たしていない場合は、分割された前者は要素なしになります。

List(1,2,3,4,5) span ( _ > 3 ) 
// (List(),List(1, 2, 3, 4, 5))

List(1,2,3,4,5) span ( _ < 3 ) 
// (List(1, 2),List(3, 4, 5))

groupBy

条件によってグループ化し、結果を Map で返します。

List("taro","jiro","kaz","takahiro") groupBy ( _.length )
// Map(3 -> List(kaz), 8 -> List(takahiro), 4 -> List(taro, jiro))

unzip

Map("taro" -> 10, "jiro" -> 7).unzip 
// (List(taro, jiro),List(10, 7))

find

最初に条件を満たした要素を Option 型で返します。

List(1,2,3).find( _ > 1 ) // Some(2)
List(1,2,3).find( _ > 2 ) // Some(3)
List(1,2,3).find( _ > 3 ) // None

exists

どれかひとつの要素が条件を満たすかどうかを判定します。

List(1,2,3) exists { _ == 1 } // true
List(1,2,3) exists { _ == 5 } // false

forall

すべての要素が条件を満たすかどうかを判定します。

List(1,2,3) forall { _ < 10 } // true
List(1,2,3) forall { _ < 2 } // false

count

条件にマッチする要素の個数を返します。

List(1,2,3) count { _ > 1 } // 2
List(1,2,3) count { i => i > 1 } // 2

size/length

個数を返します。

List(1,1,1).size // 3
List(1,1,1).length // 3

min

最小値を返します。

List(1,2,3).min // 1

max

最大値を返します。

List(1,2,3).max // 3

sum

数値の場合に合計値を返します。

List(1,2,3).sum // 6
List("foo","bar","baz").sum 
// error: could not find implicit value for parameter num: Numeric[java.lang.String]

mkString

List(1,2,3).mkString // "123"
List(1,2,3).mkString("_") // "1_2_3"
List(1,2,3).mkString("pre","_","post") // "pre1_2_3post"

toArray

List(1,2,3).toArray // Array(1,2,3)

toBuffer

List(1,2,3).toBuffer
// scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 2, 3)

toIndexedSeq

List(1,2,3).toIndexedSeq
// scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3)

toList

Array(1,2,3).toList // List(1,2,3)

toMap

List((1,2),(3,4)).toMap
// scala.collection.immutable.Map[Int,Int] = Map(1 -> 2, 3 -> 4)

toStream

scala> List(1,2,3,4,5).toStream
// scala.collection.immutable.Stream[Int] = Stream(1, ?)

par

Scala 2.9 からの機能である並列コレクション（parallel collections）を使うには par で ParIterable 型オブジェクトに変換します。

Range(1,100).par foreach { e => print(e +",") }
// 50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,13,14,15,16,17,18,19,20,21,22,23,24,7,8,9,10,11,12,1,2,3,4,5,6

view

ビューに変換すると遅延評価させることができます。最終的に force でコレクションに戻します。

List(1,2,3).view map { case e => e*2 }
// scala.collection.SeqView[Int,Seq[_]] = SeqViewM(...)

(List(1,2,3).view map { case e => e*2 }).force
// List(2, 4, 6)

collection.immutable.Iteratable

dropRight

List(1,2,3).dropRight(1) // List(1, 2)

sameElements

List(1,2,3).sameElements(List(1,2)) // false
List(1,2,3).sameElements(List(1,2,3)) // true
List(1,2,3).sameElements(List(1,2,3,4)) // false

zip

二つのコレクションをくっつけてタプルのコレクションにします。要素数は少ない方が優先されます。

List(1,2,3,4).zip(List(10,20,30)) 
// List((1,10), (2,20), (3,30))

zipWithIndex

添え字とのタプルのコレクションになります。

List(10,20,30).zipWithIndex 
// List((10,0),(20,1)(30,2))

collection.immutable.Seq

apply

List(1,2,3).apply(2) // 3
List(1,2,3)(2) // 3

contains

List(1,2,3).contains(2) // true
List(1,2,3).contains(10) // false

diff

List(1,2,3).diff(List(2,4)) // List(1,3)

startsWith

List(1,2,3).startsWith(List(1,2)) // true
List(1,2,3).startsWith(List(1,1)) // false

endsWith

List(1,2,3).endsWith(List(3)) // true

indexOf

List(0,1,2,3).indexOf(2) // 2
 List(1,1,2,2,3,3).indexOf(2) // 2

isDefinedAt

List(1,2,3).isDefinedAt(2) // true
List(1,2,3).isDefinedAt(3) // false

indices

indicesはindexの複数形です。

List(1,1,2,2,3).indices // Range(0, 1, 2, 3, 4)

distinct

List(1,2,1,2,4,4,2,3).distinct // List(1, 2, 4, 3)

reverse

List(1,2,3).reverse // List(3,2,1)

reverseMap

List(1,2,3).reverseMap { e => e * 2 } // List(6, 4, 2)

sorted

List(3,2,1,4).sorted // List(1, 2, 3, 4)

sortWith

List(4,2,1,5,3).sortWith( (a,b) => a < b ) // List(1,2,3,4,5)
List(4,2,1,5,3).sortWith( (a,b) => a > b ) // List(5,4,3,2,1)

patch

List(1,2,3) patch (1, List(4,5), 1) // List(1, 4, 5, 3)

updated

List(1,2,3).updated(1,10) // List(1,10,3)

collection.immutable.List

:::

List(1,2,3) ++ List(4) // List(1,2,3,4)
List(1,2,3) ::: List(4) // List(1,2,3,4)

::

0 +: List(1,2,3) // List(0,1,2,3)
0 :: List(1,2,3) // List(0,1,2,3)

:+

List(1,2,3) :+ 4 // List(1,2,3,4)

collection.immutable.Map

+

ペアのタプルを渡して要素を追加した Map を返します。

Map("a"->"A","b"->"B") + ("c"->"C") // Map(a->A,b->B,c->C)
Map("a"->"A","b"->"B") + Pair("c","C") // Map(a->A,b->B,c->C)
Map("a"->"A","b"->"B") + List("c","C") // error: type mismatch;

++

ペアのコレクションを渡して要素を追加した Map を返します。

Map("a"->"A","b"->"B") ++ List("c"->"C","d"->"D") // Map(a->A,b->B,c->C,d->D)
Map("a"->"A","b"->"B") ++ List(Pair("c","C"),Pair("d","D")) // Map(a->A,b->B,c->C,d->D)

ペアのコレクションでない場合は Map でないものが返ったり、エラーになったりします。

Map("a"->"A","b"->"B") ++ List("c","C","d","D") // List((a,A),(b,B),c,C,d,D)
Map("a"->"A","b"->"B") ++ ("c"->"C") // error: overloaded method value ++ with alternatives:

-

Map("a"->"A","b"->"B") - "a" // Map(b->B)
Map("a"->"A","b"->"B") - ("a","b") // Map()
Map("a"->"A","b"->"B") - ("a","b","c") // Map()

--

Map("a"->"A","b"->"B") -- List("a") // Map(b->B)
Map("a"->"A","b"->"B") -- List("a","b") // Map()
Map("a"->"A","b"->"B") -- List("a","b","c") // Map()

apply

Map("a"->"A","b"->"B").apply("a") // A
Map("a"->"A","b"->"B")("a") // A

Map("a"->"A","b"->"B").apply("c") 
// java.util.NoSuchElementException: key not found: c

get

Map("a"->"A","b"->"B").get("a") // Some("A")
Map("a"->"A","b"->"B").get("c") // None

getOrElse

Map("a"->"A","b"->"B").getOrElse("a","AAA") // "A"
Map("a"->"A","b"->"B").getOrElse("c","C") // "C"

keys

Map("a"->"A","b"->"B").keys // Set(a, b)

values

Map("a"->"A","b"->"B").values // Set(A, B)

collection.immutable.Vector

List は先頭からのアクセスには高速ですが、コレクションの後の方の要素に対する参照や変更には最適化されていないため List の長さに応じて線形に時間がかかります。

このランダムアクセスの遅さの解決を目指したのが Vector です。Vector は Scala 2.9 の時点で IndexedSeq（添字付きのSeq）のデフォルト実装になっています。

IndexedSeq(1,2,3) // Vector(1, 2, 3)
List(1,2,3).toIndexedSeq // Vector(1, 2, 3)

collection.immutable.Stream

データ構造は List とほぼ同じですが、計算が本当に必要となるまで評価を遅延させることができます。

Stream.range(1,100000) // Stream(1,?)
Stream.range(1,100000).head // 1
Stream.range(1,100000).tail // Stream(2,?)

何個目までの要素を使うかが確定していればそこまでしかメモリ上に読まれません。

// 頭から100個しかメモリにロードしない
Stream.range(1000L,100000000000L) take(100) foreach println

// 全件ロードされるのでOOMになる
Stream.range(1000L,100000000000L) filter(_<1100L) foreach println 
// java.lang.OutOfMemoryError: Java heap space

force

全体を強制的に評価します。

Stream.range(1,10) // Stream(1,?)
Stream.range(1,10).force // Stream(1,2,3,4,5,6,7,8,9,10)

#::

Listなどでの「::」「:::」のような連結処理をStreamでは「#::」で記述します。

1 #:: Stream(2,3) // Stream(1, ?)

#:::

Stream(1,2) #::: Stream(3,4) // Stream(1, ?)