読者です 読者をやめる 読者になる 読者になる

無限大な夢のあと

テニスとアニメが大好きな厨二病SEのブログ

ドワンゴの新卒エンジニア向けの研修資料でScalaに入門 その8(Scalaのコレクションライブラリ(immutableとmutable)前半

Scalaを業務で使うことになり、以下のドワンゴオリジナルの新卒エンジニア向けの研修資料でScalaを本格的に勉強してみることにした。
https://dwango.github.io/scala_text/index.htmldwango.github.io

可能な限りGolangとの比較も入れていきます。

学んだことをとにかく走り書きしていきます。
Scalaのコレクションライブラリ(immutableとmutable)】
・概要

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はパフォーマンス上必要になる場合以外はあまり積極的に使うものではありません。

これは頭に留めておきたい。
ClassTagと言うものについては以下を参照。
Scala ClassTagメモ(Hishidama's Scala ClassTag Memo)

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

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

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

Javaの時にやったような配列の入れ替えの実装。




・Range

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

scala> 1 to 5
res8: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3, 4, 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, 2, 3, 4)

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

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

rangeはGolangにもあるし、JavaだとGuavaのライブラリにもあった気がする。
untilでは含まないということだけ覚えておこう。

・List

さて、導入として大抵の言語にあるArrayを出しましたが、ScalaではArrayを使うことはそれほど多くありません。代わりにListや Vectorといったデータ構造をよく使います(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の値を更新することなく色々な操作ができることがわかるでしょう。

JavaだとGuavaで使っているImmutableListと同じなので、使う分には問題なし。

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の後ろにくっつけるのではなく、先頭にくっつけるメソッドの説明が先なのはNilの説明の都合上かな?

・++:List同士の連結

    1. は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. は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の仕様は混乱しやすいので注意してください。

これは確かにはまりそう。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)とほとんど同じですが、startとendに囲まれた文字列を返すところが異なります。

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

ここは問題なし。

・mkstringの練習問題

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

start,...,end

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

def joinByComma(start: Int, end: Int): String = {
  (start to end).mkString

}

ここも問題なし。

・foldLeft:左からの畳み込み

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

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

となります。zがfoldLeftの結果の初期値で、リストを左からたどりながら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を用いて実装することができます。

うん、ここはUndersocre.jsで勉強した時にふわっとやったので覚えてる。
使いこなせるよう問題をいくつか解きたい。

foldLeftの練習問題

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

def reverse[T](list: List[T]): List[T] = list.foldLeft(Nil: List[T])((a, b) => b :: a)

OK。



・foldRight:右からの畳み込み

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

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

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

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

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

foldLeftとの使い分けがそこまでわからず。


foldRightの練習問題 その1

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

scala>  def sum(list: List[Int]): Int = list.foldRight(0)((a,b) => a+b)

すんなりいけたので、問題なし。


foldRightの練習問題 その2

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

scala> def mul(list: List[Int]): Int = list.foldRight(1)((a,b) =>a * b)
mul: (list: List[Int])Int

これもすんなりいけたので、問題なし。

foldRightの練習問題 その3

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

scala>def mkString[T](list: List[T])(sep: String): String = list match {
  case Nil => ""
  case x::xs => xs.foldLeft(x.toString){(x, y) => x + sep + y}
}

ここは解けず。
回答例を参考にする。
x:xsがListを表すことができて、case matchで引っかかるそう。
9.1 リストの使用 (Using Lists) - プログラミング言語Scala 日本語情報サイト


引き続き頑張る。

Scalaスケーラブルプログラミング第3版

Scalaスケーラブルプログラミング第3版

Programming in Scala: Updated for Scala 2.12

Programming in Scala: Updated for Scala 2.12

Scalaパズル 36の罠から学ぶベストプラクティス

Scalaパズル 36の罠から学ぶベストプラクティス

SCALAプログラミング入門

SCALAプログラミング入門