コレクションライブラリ(immutableとmutable)

Scalaには配列(Array)やリスト(List)、連想配列(Map)、集合(Set)を扱うための豊富なライブラリがあります。これを使いこなすことで、Scalaでのプログラミングは劇的に楽になります。注意しなければならないのは、Scalaでは一度作成したら変更できない(immutable)なコレクションと変更できる通常のコレクション(mutable)があることです。皆さんはmutableなコレクションに馴染んでいるかと思いますが、Scalaで関数型プログラミングを行うためには、immutableなコレクションを活用する必要があります。

immutableなコレクションを使うのにはいくつものメリットがあります

  • 関数型プログラミングで多用する再帰との相性が良い
  • 高階関数を用いて簡潔なプログラムを書くことができる
  • 一度作ったコレクションが知らない箇所で変更されていない事を保証できる
  • 並行に動作するプログラムの中で、安全に受け渡しすることができる

mutableなコレクションを効果的に使えばプログラムの実行速度を上げることができますが、mutableなコレクションをどのような場面で使えばいいかは難しい問題です。

この節では、Scalaのコレクションライブラリに含まれる以下のものについての概要を説明します。

  • Array(mutable)
  • List(immutable)
  • Map(immutable)・Map(mutable)
  • Set(immutable)・ Set(mutable)

Array

まずは大抵のプログラミング言語にある配列です。

scala> val arr = Array(1, 2, 3, 4, 5)
arr: Array[Int] = Array(1, 2, 3, 4, 5)

これで1から5までの要素を持った配列がarrに代入されました。Scalaの配列は、他の言語のそれと同じように要素の中身を入れ替えることができます。配列の添字は0から始まります。なお、配列の型を指定しなくて良いのは、Array(1, 2, 3, 4, 5)の部分で、要素型がIntであるに違いないとコンパイラが型推論してくれるからです。型を省略せずに書くと

scala> val arr = Array[Int](1, 2, 3, 4, 5)
arr: Array[Int] = Array(1, 2, 3, 4, 5)

となります。ここで、[Int]の部分は型パラメータと呼びます。Arrayだけだとどの型かわからないので、[Int]を付けることでどの型のArrayかを指定しているわけです。この型パラメータは型推論を補うために、色々な箇所で出てくるので覚えておいてください。しかし、この場面では、Arrayの要素型はIntだとわかっているので、冗長です。次に要素へのアクセスと代入です。

scala> arr(0) = 7

scala> arr
res1: Array[Int] = Array(7, 2, 3, 4, 5)

scala> arr(0)
res2: Int = 7

他の言語だとarr[0]のようにしてアクセスすることが多いので最初は戸惑うかもしれませんが、慣れてください。配列の0番目の要素がちゃんと7に入れ替わっていますね。

配列の長さはarr.lengthで取得することができます。

scala> arr.length
res3: Int = 5

Array[Int]はJavaではint[]と同じ意味です。Scalaでは、配列などのコレクションの要素型を表記するとき Collection[ElementType]のように一律に表記し、配列も同じように記述するのです。Javaでは配列型だけ特別扱いするのに比べると統一的だと言えるでしょう。

ただし、あくまでも表記上はある程度統一的に扱えますが、実装上はJVMの配列であり、 要素が同じでもequalsの結果がtrueにならない, 生成する際にClassTagというものが必要 などのいくつかの罠があるので、Arrayはパフォーマンス上必要になる場合以外はあまり積極的に使うものではありません。

練習問題

配列のi番目の要素とj番目の要素を入れ替えるswapArrayメソッドを定義してみましょう。swapArrayメソッドの宣言は

def swapArray[T](arr: Array[T])(i: Int, j: Int): Unit = ???

となります。ijが配列の範囲外である場合は特に考慮しなくて良いです。

Range

Rangeは範囲を表すオブジェクトです。Rangeは直接名前を指定して生成するより、toメソッドとuntilメソッドを用いて呼びだすことが多いです。また、toListメソッドを用いて、その範囲の数値の列を後述するListに変換することができます。では、早速REPLでRangeを使ってみましょう。

scala> 1 to 5
res8: scala.collection.immutable.Range.Inclusive = Range 1 to 5

scala> (1 to 5).toList
res9: List[Int] = List(1, 2, 3, 4, 5)

scala> 1 until 5
res10: scala.collection.immutable.Range = Range 1 until 5

scala> (1 until 5).toList
res11: List[Int] = List(1, 2, 3, 4)

toは右の被演算子を含む範囲を、untilは右の被演算子を含まない範囲を表していることがわかります。また、RangetoListで後述するListに変換することができることもわかります。

List

さて、導入として大抵の言語にあるArrayを出しましたが、ScalaではArrayを使うことはそれほど多くありません。代わりにListVectorといったデータ構造をよく使います(Vectorについては後述します)。Listの特徴は、一度作成したら中身を変更できない(immutable)ということです。中身を変更できないデータ構造(永続データ構造とも呼びます)はScalaがサポートしている関数型プログラミングにとって重要な要素です。それではListを使ってみましょう。

scala> val lst = List(1, 2, 3, 4, 5)
lst: List[Int] = List(1, 2, 3, 4, 5)
scala> lst(0) = 7
<console>:14: error: value update is not a member of List[Int]
       lst(0) = 7
       ^

見ればわかるように、Listは一度作成したら値を更新することができません。しかし、Listは値を更新することができませんが、あるListを元に新しいListを作ることができます。これが値を更新することの代わりになります。以降、Listに対して組み込みで用意されている各種操作をみていくことで、Listの値を更新することなく色々な操作ができることがわかるでしょう。

Nil:空のList

まず最初に紹介するのはNilです。Scalaで空のListを表すにはNilというものを使います。Rubyなどではnilは言語上かなり特別な意味を持ちますが、Scalaではデフォルトでスコープに入っているということ以外は特別な意味はなく単にobjectです。Nilは単体では意味がありませんが、次に説明する::と合わせて用いることが多いです。

:: - Listの先頭に要素をくっつける

::(コンスと読みます)は既にあるListの先頭に要素をくっつけるメソッドです。これについては、REPLで結果をみた方が早いでしょう。

scala> val a1 = 1 :: Nil
a1: List[Int] = List(1)

scala> val a2 = 2 :: a1
a2: List[Int] = List(2, 1)

scala> val a3 = 3 :: a2
a3: List[Int] = List(3, 2, 1)

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

scala> val a5 = 5 :: a3
a5: List[Int] = List(5, 3, 2, 1)

付け足したい要素を::を挟んでListの前に書くことでListの先頭に要素がくっついていることがわかります。ここで、::はやや特別な呼び出し方をするメソッドであることを説明しなければなりません。まず、Scalaでは1引数のメソッドは中置記法で書くことができます。それで、1 :: Nil のように書くことができるわけです。次に、メソッド名の最後が:で終わる場合、被演算子の前と後ろをひっくり返して右結合で呼び出します。たとえば、

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

は、実際には、

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

のように解釈されます。Listの要素が演算子の前に来て、一見数値のメソッドのように見えるのにListのメソッドとして呼び出せるのはそのためです。

++:List同士の連結

++はList同士を連結するメソッドです。これもREPLで見た方が早いでしょう。

scala> List(1, 2) ++ List(3, 4)
res15: List[Int] = List(1, 2, 3, 4)

scala> List(1) ++ List(3, 4, 5)
res16: List[Int] = List(1, 3, 4, 5)

scala> List(3, 4, 5) ++ List(1)
res17: List[Int] = List(3, 4, 5, 1)

++は1引数のメソッドなので、中置記法で書いています。また、末尾が:で終わっていないので、たとえば、

scala> List(1, 2) ++ List(3, 4)
res18: List[Int] = List(1, 2, 3, 4)

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

と同じ意味です。大きなList同士を連結する場合、計算量が大きくなるのでその点には注意した方が良いです。

mkString:文字列のフォーマッティング

このメソッドはScalaで非常に頻繁に使用され皆さんも、Scalaを使っていく上で使う機会が多いであろうメソッドです。このメソッドは引数によって多重定義されており、3バージョンあるのでそれぞれを紹介します。

mkString

引数なしバージョンです。このメソッドは、単にListの各要素を左から順に繋げた文字列を返します。

scala> List(1, 2, 3, 4, 5).mkString
res20: String = 12345

注意しなければならないのは、引数なしメソッドのmkString()を付けて呼びだすことができない という点です。たとえば、以下のコードは、若干分かりにくいエラーメッセージがでてコンパイルに失敗します。

scala> List(1, 2, 3, 4, 5).mkString()
<console>:13: error: overloaded method value mkString with alternatives:
  => String <and>
  (sep: String)String <and>
  (start: String,sep: String,end: String)String
 cannot be applied to ()
       List(1, 2, 3, 4, 5).mkString()
                           ^

Scalaの0引数メソッドは()なしと ()を使った定義の二通りあって、前者の形式で定義されたメソッドは()を付けずに呼び出さなければいけません。逆に、()を使って定義されたメソッドは、()を付けても付けなくても良いことになっています。このScalaの仕様は混乱しやすいので注意してください。

mkString(sep: String)

引数にセパレータ文字列sepを取り、Listの各要素をsepで区切って左から順に繋げた文字列を返します。

scala> List(1, 2, 3, 4, 5).mkString(",")
res22: String = 1,2,3,4,5

mkString(start: String, sep: String, end: String)

mkString(sep)とほとんど同じですが、startendに囲まれた文字列を返すところが異なります。

scala> List(1, 2, 3, 4, 5).mkString("[", ",", "]")
res23: String = [1,2,3,4,5]

練習問題

mkStringを使って、最初の数startと最後の数endを受け取って、

start,(start+1),(start+2)...,end

となるような文字列を返すメソッドjoinByCommaを定義してみましょう(ヒント:Range にもmkStringメソッドはあります)。

joinByComma(1,5)  // 1,2,3,4,5
def joinByComma(start: Int, end: Int): String = {
  ???
}

foldLeft:左からの畳み込み

foldLeftメソッドはListにとって非常に基本的なメソッドです。他の様々なメソッドをfoldLeftを使って実装することができます。foldLeftの宣言をScalaのAPIドキュメントから引用すると、

def foldLeft[B](z: B)(f: (B, A) ⇒ B): B

となります。zfoldLeftの結果の初期値で、リストを左からたどりながらfを適用していきます。foldLeftについてはイメージが湧きにくいと思いますので、List(1, 2, 3).foldLeft(0)((x, y) => x + y)の結果を図示します。

       +
      / \
     +   3
    / \
   +   2
  / \
 0   1

この図で、

   +
  / \
 0   1

+に0と1を与えて適用するということを意味します。リストの要素を左から順にfを使って「畳み込む」(fold は英語で畳み込むという意味を持ちます)状態がイメージできるでしょうか。foldLeftは汎用性の高いメソッドで、たとえば、Listの要素の合計を求めたい場合は

scala> List(1, 2, 3).foldLeft(0)((x, y) => x + y)
res25: Int = 6

Listの要素を全て掛けあわせた結果を求めたい場合は

scala> List(1, 2, 3).foldLeft(1)((x, y) => x * y)
res26: Int = 6

とすることで求める結果を得ることができます1。その他にも様々な処理をfoldLeftを用いて実装することができます。

練習問題

foldLeftを用いて、Listの要素を反転させる次のシグニチャを持ったメソッドreverseを実装してみましょう:

def reverse[T](list: List[T]): List[T] = ???

foldRight:右からの畳み込み

foldLeftListの左からの畳み込みだったのに対して、foldRightは右からの畳込みです。foldRightの宣言を ScalaのAPIドキュメントから参照すると、

def foldRight[B](z: B)(op: (A, B) ⇒ B): B

となります。foldRightに与える関数であるopの引数の順序がfoldLeftの場合と逆になっている事に注意してください。 foldRightList(1, 2, 3).foldRight(0)((y, x) => y + x)とした場合の様子を図示すると次のようになります。

   +
  / \
 1   +   
    / \
   2   +   
      / \
     3   0

ちょうどfoldLeftと対称になっています。foldRightも非常に汎用性の高いメソッドで、多くの処理をfoldRightを用いて実装することができます。

練習問題

Listの全ての要素を足し合わせるメソッドsumfoldRightを用いて実装してみましょう。sumの宣言は次のようになります。なお、Listが空のときは0を返してみましょう。

def sum(list: List[Int]): Int = ???

練習問題

Listの全ての要素を掛け合わせるメソッドmulfoldRightを用いて実装してみましょう。mulの宣言は次のようになります。なお、Listが空のときは1を返してみましょう。

scala> def mul(list: List[Int]): Int = ???
mul: (list: List[Int])Int

練習問題

mkStringを実装してみましょう。mkStringそのものを使ってはいけませんが、foldLeftfoldRightなどのListに定義されている他のメソッドは自由に使って構いません。ListのAPIリファレンス を読めば必要なメソッドが載っています。実装するmkStringの宣言は

def mkString[T](list: List[T])(sep: String): String = ???

となります。残りの2つのバージョンのmkStringは実装しなくても構いません。

map:各要素を加工した新しいListを返す

mapメソッドは、1引数の関数を引数に取り、各要素に関数を適用した結果できた要素からなる新たなListを返します。ためしにList(1, 2, 3, 4, 5)の各要素を2倍してみましょう。

scala> List(1, 2, 3, 4, 5).map(x => x * 2)
res31: List[Int] = List(2, 4, 6, 8, 10)

x => x * 2の部分は既に述べたように、無名関数を定義するための構文です。メソッドの引数に与える短い関数を定義するときは、 Scalaでは無名関数をよく使います。Listの全ての要素に何らかの処理を行い、その結果を加工するという処理は頻出するため、mapは Scalaのコレクションのメソッドの中でも非常によく使われるものになっています。

練習問題

次のシグニチャを持つmapメソッドをfoldLeftreverseを使って実装してみましょう:

def map[T, U](list: List[T])(f: T => U): List[U] = ???

filter:条件に合った要素だけを抽出した新しいListを返す

filterメソッドは、Boolean型を返す1引数の関数を引数に取り、各要素に関数を適用し、trueになった要素のみを抽出した新たなListを返します。List(1, 2, 3, 4, 5)から奇数だけを抽出してみましょう。

scala> List(1, 2, 3, 4, 5).filter(x => x % 2 == 1)
res32: List[Int] = List(1, 3, 5)

練習問題

次のシグニチャを持つfilterメソッドをfoldLeftreverseを使って実装してみましょう:

def filter[T](list: List[T])(f: T => Boolean): List[T] = ???

find:条件に合った最初の要素を返す

findメソッドは、Boolean型を返す1引数の関数を引数に取り、各要素に前から順番に関数を適用し、最初にtrueになった要素を Someでくるんだ値をOption型として返します。1つの要素もマッチしなかった場合NoneOption型として返します。 List(1, 2, 3, 4, 5)から最初の奇数だけを抽出してみましょう

scala> List(1, 2, 3, 4, 5).find(x => x % 2 == 1)
res33: Option[Int] = Some(1)

後で説明されることになりますが、Option型はScalaプログラミングの中で重要な要素であり頻出します。

takeWhile:先頭から条件を満たしている間を抽出する

takeWhileメソッドは、Boolean型を返す1引数の関数を引数に取り、前から順番に関数を適用し、結果がtrueの間のみからなるListを返します。List(1, 2, 3, 4, 5)の5より前の4要素を抽出してみます。

scala> List(1, 2, 3, 4, 5).takeWhile(x => x != 5)
res34: List[Int] = List(1, 2, 3, 4)

count:Listの中で条件を満たしている要素の数を計算する

countメソッドは、Boolean型を返す1引数の関数を引数に取り、全ての要素に関数を適用して、trueが返ってきた要素の数を計算します。例としてList(1, 2, 3, 4, 5)の中から偶数の数(2になるはず)を計算してみます。

scala> List(1, 2, 3, 4, 5).count(x => x % 2 == 0)
res35: Int = 2

練習問題

次のシグニチャを持つcountメソッドをfoldLeftを使って実装してみましょう:

def count[T](list: List[T])(f: T => Boolean): Int = ???

flatMap:Listをたいらにする

flatMapは一見少し変わったメソッドですが、後々重要になってくるメソッドなので説明しておきます。flatMapの宣言はScalaのAPIドキュメントから参照すると、

final def flatMap[B](f: (A) ⇒ GenTraversableOnce[B]): List[B]

となります。ここで、GenTraversableOnce[B]という変わった型が出てきていますが、ここではあらゆるコレクション(要素の型はB型である)を入れることができる型程度に考えてください。さて、flatMapの引数fの型は(A) => GenTraversableOnce[B]です。flatMapはこれを使って、各要素にfを適用して、結果の要素からなるコレクションを分解してListの要素にします。これについては、実際に見た方が早いでしょう。

scala> List(List(1, 2, 3), List(4, 5)).flatMap{e => e.map{g => g + 1}}
res36: List[Int] = List(2, 3, 4, 5, 6)

ネストしたListの各要素にflatMapの中でmapを適用して、Listの各要素に1を足したものをたいらにしています。これだけだとありがたみがわかりにくいですが、ちょっと形を変えてみると非常に面白い使い方ができます:

scala> List(1, 2, 3).flatMap{e => List(4, 5).map(g => e * g)}
res37: List[Int] = List(4, 5, 8, 10, 12, 15)

List(1, 2, 3)List(4, 5)の2つのListについてループし、各々の要素を掛けあわせた要素からなるListを抽出しています。実は、 for-comprehension

for(x <- col1; y <- col2;) yield z

col1.flatMap{x => col2.map{y => z}}

のシンタックスシュガーだったのです。すなわち、ある自分で定義したデータ型にflatMapmapを(適切に)実装すれば for構文の中で使うことができるのです。

Listの性能特性

Listの性能特性として、Listの先頭要素へのアクセスは高速にできる反面、要素へのランダムアクセスや末尾へのデータの追加は Listの長さに比例した時間がかかってしまうということが挙げられます。Listは関数型プログラミング言語で最も基本的なデータ構造で、どの関数型プログラミング言語でもたいていはListがありますが、その性能特性には十分注意して扱う必要があります。特に他の言語のプログラマはうっかりListの末尾に要素を追加するような遅いプログラムを書いてしまうことがあるので注意する必要があります。

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

scala> 5 :: List(1, 2, 3, 4) // Listの先頭のセルに新しいをくっつける
res39: List[Int] = List(5, 1, 2, 3, 4)

scala> List(1, 2, 3, 4) :+ 5 // 注意!末尾への追加は、Listの要素数分かかる
res40: List[Int] = List(1, 2, 3, 4, 5)

紹介したメソッドについて

mkStringをはじめとしたListの色々なメソッドを紹介してきましたが、実はこれらの大半はList特有ではなく、既に紹介したRangeArray、これから紹介する他のコレクションでも同様に使うことができます。何故ならばこれらの操作の大半は特定のコレクションではなく、コレクションのスーパータイプである共通のトレイト中に宣言されているからです。もちろん、Listに要素を加える処理とSetに要素を加える処理(Setに既にある要素は加えない)のように、中で行われる処理が異なることがあるので、その点は注意する必要があります。詳しくはScalaのAPIドキュメントを探索してみましょう。

Vector

Vectorは少々変わったデータ構造です。Vectorは一度データ構造を構築したら変更できないimmutableなデータ構造です。要素へのランダムアクセスや長さの取得、データの挿入や削除、いずれの操作も十分に高速にできる比較的万能なデータ構造です。immutableなデータ構造を使う場合は、まずVectorを検討すると良いでしょう。

scala> Vector(1, 2, 3, 4, 5) //どの操作も「ほぼ」一定の時間で終わる
res41: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4, 5)

scala> 6 +: Vector(1, 2, 3, 4, 5)
res42: scala.collection.immutable.Vector[Int] = Vector(6, 1, 2, 3, 4, 5)

scala> Vector(1, 2, 3, 4, 5) :+ 6
res43: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4, 5, 6)

scala> Vector(1, 2, 3, 4, 5).updated(2, 5)
res44: scala.collection.immutable.Vector[Int] = Vector(1, 2, 5, 4, 5)

Map

Mapはキーから値へのマッピングを提供するデータ構造です。他の言語では辞書や連想配列と呼ばれたりします。 ScalaではMapとして一度作成したら変更できないimmutableなMapと変更可能なmutableなMapの2種類を提供しています。

scala.collection.immutable.Map

Scalaで何も設定せずにただMapと書いた場合、scala.collection.immutable.Mapが使われます。その名の通り、一度作成すると変更することはできません。内部の実装としては主にscala.collection.immutable.HashMapscala.collection.immutable.TreeMapの2種類がありますが、通常はHashMapが使われます。

scala> val m = Map("A" -> 1, "B" -> 2, "C" -> 3)
m: scala.collection.immutable.Map[String,Int] = Map(A -> 1, B -> 2, C -> 3)

scala> m.updated("B", 4) //一見元のMapを変更したように見えても
res45: scala.collection.immutable.Map[String,Int] = Map(A -> 1, B -> 4, C -> 3)

scala> m // 元のMapはそのまま
res46: scala.collection.immutable.Map[String,Int] = Map(A -> 1, B -> 2, C -> 3)

scala.collection.mutable.Map

Scalaの変更可能なMapscala.collection.mutable.Mapにあります。実装としては、scala.collection.mutable.HashMapscala.collection.mutable.LinkedHashMap、リストをベースにしたscala.collection.mutable.ListMapがありますが、通常は HashMapが使われます。

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

scala> val m = mutable.Map("A" -> 1, "B" -> 2, "C" -> 3)
m: scala.collection.mutable.Map[String,Int] = Map(A -> 1, C -> 3, B -> 2)

scala> m("B") = 5 // B -> 5 のマッピングに置き換える

scala> m // 変更が反映されている
res48: scala.collection.mutable.Map[String,Int] = Map(A -> 1, C -> 3, B -> 5)

Set

Setは値の集合を提供するデータ構造です。Setの中では同じ値が2つ以上存在しません。たとえば、IntSetの中には1が2つ以上含まれていてはいけません。REPLでSetを作成するための式を入力すると、

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

重複した1が削除されて、1が1つだけになっていることがわかります。

scala.collection.immutable.Set

Scalaで何も設定せずにただSetと書いた場合、scala.collection.immutable.Setが使われます。immutableなMapの場合と同じく、一度作成すると変更することはできません。内部の実装としては、主に scala.collection.immutable.HashSetscala.collection.immutable.TreeSet の2種類がありますが、通常はHashSetが使われます。

scala> val s = Set(1, 2, 3, 4, 5)
s: scala.collection.immutable.Set[Int] = Set(5, 1, 2, 3, 4)

scala> s - 5 // 5を削除した後も
res50: scala.collection.immutable.Set[Int] = Set(1, 2, 3, 4)

scala> s // 元のSetはそのまま
res51: scala.collection.immutable.Set[Int] = Set(5, 1, 2, 3, 4)

scala.collection.mutable.Set

Scalaの変更可能なSetscala.collection.mutable.Setにあります。主な実装としては、scala.collection.mutable.HashSetscala.collection.mutable.TreeSetがありますが、通常はHashSetが使われます。

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

scala> val s = mutable.Set(1, 2, 3, 4, 5)
s: scala.collection.mutable.Set[Int] = Set(1, 5, 2, 3, 4)

scala> s -= 5 // 5 を削除したら
res52: s.type = Set(1, 2, 3, 4)

scala> s // 変更が反映される
res53: scala.collection.mutable.Set[Int] = Set(1, 2, 3, 4)

その他資料

さらにコレクションライブラリについて詳しく知りたい場合は、以下の公式のドキュメントなどを読みましょう http://docs.scala-lang.org/ja/overviews/collections/introduction.html

1. ただし、これはあくまでもfoldLeftの例であって、要素の和や積を求めたい場合に限って言えばもっと便利なメソッドが標準ライブラリに存在するので、実際にはこの例のような使い方はしません

results matching ""

    No results matching ""