ともちんの Tech ブログ

Scala コレクション - Seq の定義を見よう

Scala Collection

はじめに

コレクションは、様々なデータを格納するための Scala において重要な概念です。

コレクションには主に、リストや配列などを含む Seq、ハッシュマップやツリーマップを含む Map、そして Set の3つのコレクションがあります。

本エントリでは、不変 (immutable) コレクションと可変 (mutable) コレクションの違いについて見た上で、コレクションクラス全体の階層構造を説明し、コレクションクラスの中でもイメージしやすい Seq (sequence) の定義、各種メソッドの定義について見ていきます。

なお、Scala のバージョンは 2.12.x のものとします [1]。2020年5月時点での最新のバージョンは2.13です。

immutable と mutable

コレクションクラスには、不変 (immutable) なものと可変 (mutable) なものがあります。

不変コレクションは一度定義されたら書き換えることのできないコレクションで、可変コレクションは何度も書き換えることのできるコレクションです。書き換えることができるとは、既存のコレクションに値を追加したり、値を更新したり、値を削除したりすることができることを意味します。

Java や C などの言語を使っている人は、配列やリストといったオブジェクトは値を書き換えられてなんぼのイメージがあるかと思います。

しかし、Scala では一般的に、不変コレクションが推奨されています。

その理由としては、不変コレクションは値が変わらないのでコードを読み解くのが容易になること、可変コレクションを使うと同じメソッドに同じ引数を与えても文脈で異なる値が返ってきてしまうこと、などが挙げられます。

ですので、特に理由がない限りは不変コレクションを使いましょう。

不変コレクションはデフォルトで利用できるので、利用する際は scala.collection.immutable をインポートしなくて良いです。可変コレクションを利用したい場合は scala.collection.mutable をインポートする必要があります。

コレクションクラスの階層構造

次に、コレクションクラスの階層構造について見ていきましょう。

コレクションには階層構造があります。Seq や Map、Set は同じ第3階層に属しており、一つの Iterable トレイトを継承します。Iterable は、反復可能であることを意味するコレクションです。

Iterable はさらに、Traversable トレイトを継承します。Traversable は、走査可能であることを意味するコレクションです。

次の図は、不変なコレクションクラスの階層構造を表した図です [2]。薄い水色のノードがトレイト、紺色のノードが具象クラスを表します。最上位層に Traversable トレイトが位置しており、それを Iterable トレイトが継承し、その下に Seq、Map、Set が位置していることがわかります。

コレクションクラスの階層構造

では、Traversable と Iterable がどんな役割を担っているのかについてみていきましょう。

Traversable トレイト

Traversable は走査可能なモノを表します [3]。ここで、走査 (traverse) とは、木構造などでノードを1つずつ調べることをいいます。すなわち、Traversable は、それが持つ要素を1つずつ調べられる概念です。

Traversable トレイトは以下のように定義されます。

親クラスの TraversableLike は、Traversable トレイトに対する操作 (メソッド) を定義したものです。Traversable[A] を返すような、ビルダーを用いてコレクションのインスタンスを生成するためのメソッドが主に定義されています。

ミックスインの GenTraversable は、並行コレクションのためのトレイトです。並行コレクションは難しい概念ですので、ここでは言及しません。

TraversableOnce はビルダー (コレクションのインスタンスを作るもの) を必要としない操作を定義したもので、Iterator と Traversable のコードの重複を削除するためのものです。主に、要素の一部またはすべてを走査して派生値を返したり、フォールドしたり、変換、その他の操作をしたりするメソッドが定義されています。

GenericTraversableTemplate は、全てのコレクションクラスのコンパニオンオブジェクトのためのテンプレートトレイトです。

コレクションを使う分には、コレクションを操作するメソッド定義が書かれてある TraversableLike と TraversableOnce のコードを読めば良いと思います。

Traversable トレイトの抽象メソッドは foreach のみで、Traversable を実装するコレクションはこのメソッドを実装するだけでよいです。

Iterable トレイト

Iterable は反復可能なモノを表します [4]。ここで、反復 (Iterate) とは、for 式などで要素を1つずつ取り出して繰り返しアクセスすることをいいます。すなわち、Iterable は、それが持つ要素に1つずつ繰り返してアクセスすることのできる概念です。

Iterable トレイトは Traversable トレイトを継承しており、Seq、Map、Set の親クラスとなっているコレクションです。以下のように定義されています。

このトレイトの全てのメソッドは、コレクションの要素を1つずつ返す抽象メンバ Iterator に基づいています。例えば、head や foreach は次のように Iterator を使って定義されています。

Iterable は、grouped メソッドと sliding メソッドを用いて Iterator を返すことができます。

grouped は、コレクションを分割した Iterator を返すメソッドです。

sliding は、指定したサイズのサブコレクションを取得する Iterator を返すメソッドです。

Seq トレイト

Seq は、長さ (length) があり、それぞれの要素に0から始まる添字 (index) がある Iterable の一種です [5]。

Seq トレイトには LinearSeq と IndexedSeq という2つの子トレイトがあります。

これらの Seq はそれぞれ異なった性能特性を持ちます。線形列 (linear sequence) LinearSeq は効率的な head と tail 演算を持ち、一方 添字付き列 (indexed sequence) IndexedSeq は効率的な apply、length、および update 演算を持ちます。

線形列の具象不変クラスには List と Stream があります。添字付き列には Array と ArrayBuffer があります。

Seq トレイトは以下のように定義されます。

Seq の各種メソッド

ここでは、Seq を触るために必要なメソッドの定義について見ていきます。内部でどんな処理をしていて、何が返されるのかを理解しましょう。

Seq の初期化

Seq のインスタンスを作るには、格納したい要素を Seq() で包みます。

空の Seq のインスタンスを作るには、Seq.empty メソッドを用います。

apply メソッド - 添字から Seq の要素を取得する

apply メソッドは、添字から Seq の要素を取得するメソッドです。

apply メソッドであるので、先頭から2番目の要素を取得したい場合は Seq(1) とすれば良いです。

head メソッド、headOption メソッド - Seq の先頭要素を取得するメソッド

head メソッドと headOption メソッドは、Seq の先頭要素の値を取得するメソッドです。

head メソッドは Iterator によって実装されています。

Iterator.next メソッドは Iterator の実装によりバリエーションがあります。しかし、head メソッドを理解する分には

  • Iterator.next は、先頭要素がある場合は先頭要素を返す
  • Iterator.next は、先頭要素がない場合は例外 NoSuchElementException を発生させる

と覚えておけば十分です。

例外が発生すると、例外を捕捉しない限りアプリケーションが落ちてしまうので、より安全な headOption メソッドがよく使われます。

headOption メソッドは、Seq が空なら None を返し、要素があるなら Some(head) を返します。

last メソッド、lastOption メソッド - Seq の要素を取得するメソッド

last メソッドと lastOption メソッドは、Seq の末尾要素を取得するメソッドです。

head 同様、空の Seq に対して last メソッドは例外を発生させます。

lastOption メソッドは末尾要素を Option で包んで返します。

map メソッド - Seq の要素を変換する

map メソッドを使えば、コレクションの各要素になんらかの処理を行うことができます。

map メソッドの定義は次のようになっています。引数として関数 f: A => B を受け取り、ビルダーを生成し、コレクションの各要素に対して f を適用した上で、その結果を返す、というメソッドです。

ここで、ビルダーは何をしているのでしょうか？

CanBuildFrom[-From, -Elem, +To] は、元のコレクションの型 From が利用可能なとき、型 Elem の要素からなる型 To のコレクションを生成します。Elem は例えば Int や Boolean など、To は例えば List[Int] や TreeMap[Int, String] などです。

CanBuildFrom の apply メソッドは、Builder[Elem, To] すなわち Builder[Int, List[Int] のようなものを生成します。

なお、CanBuildFrom は2.13から非推奨となり、代わりに BuildFrom を使います。

Builder は、scala.collection.mutable パッケージに定義されています。

Builder トレイトは以下のように定義されています。

Builder は空の状態から始まり、要素が追加されるなどの操作がされたあと、result メソッドによってその結果が返されます。なお、Seq は Builder として scala.collection.mutable.ListBuffer を用いています。

以上のことから、Traversable[+A, +Repr]#map メソッドは以下のような処理を行なっていることがわかります。

  • 元のコレクション Repr から型 B の要素からなるコレクション That を生成するビルダーのインスタンスを生成する
  • コレクションの各要素 x に対して、関数 f を実行した結果 f(x) をビルダーにそれぞれ保存する
  • Builder.result によって、全要素に関数 f を実行した結果をコレクションとして返す

flatten メソッド - 入れ子になった Seq を平滑化する

flatten メソッドは、入れ子になった Seq を平滑化するメソッドです。

Seq の flatten メソッドの定義については、以下の記事で述べています。よければ。

taretmch.hatenablog.com

find メソッド - Seq の要素を検索する

find メソッドは、IterableLike トレイトでオーバーライドされています。find は、引数として命題関数を受け取り、結果を Option でくるんで返すメソッドです。条件に合致する要素がなければ None が返されます。

上記の find メソッドでは、Iterator.find を呼び出しています。

Iterator.find メソッドは、列の先頭から要素を検索し、条件を満たすものがあればそれを返し、処理を終了します。

filter メソッド - Seq の要素を絞り込む

filter メソッドは、条件を満たす要素を抽出し、その列を返すメソッドです。

filter は、TraversableLike で以下のように定義されています。List に対しては List 専用のフィルタを呼び出し、それ以外のコレクションに対しては Builder を用いて要素を1つずつ検証しています。

collect メソッド - Seq の要素を条件付きで変換する

collect メソッドは、条件を満たす要素に対して変換を施したものをコレクションとしてまとめ直して返すメソッドです。

collect メソッドは TraversableLike で以下のように定義されています。collect メソッドは、引数として部分関数 pf: PartialFunction[A, B] をとります。

ここで、部分関数 PartialFunction[A, B] とは、定義域に型 A の全ての値が含まれているわけではない関数のことをいいます。言い換えると、特定の引数のみを処理する関数です。

部分関数は、次のような形で表現されます。

collectFirst メソッド - 条件を満たす最初の要素を変換する

collectFirst メソッドは、条件を満たす最初に要素に対して変換を施したものを返すメソッドです。

collectFirst メソッドは、TraversableOnce で以下のように定義されています。部分関数を引数に取り、結果を Option でくるんで返します。

++ メソッド - Seq どうしを連結する

++ メソッドは、2つのコレクションを連結させるメソッドです。次のように使います。

foldLeft メソッド - Seq の要素を先頭から畳み込み演算する

foldLeft メソッドは、コレクションの先頭から順に畳み込み演算を行うメソッドです。

foldLeft メソッドは、TraversableOnce[+A] で以下のように定義されています。引数として初期値 z: B、行いたい処理 op: (B, A) => B をとり、コレクションの先頭から畳み込み演算を行います。

コレクションの各要素に foreach でアクセスし、それぞれに対して folder 関数を実行するように実装されています。folder 関数は、計算結果の初期値として z を持っており、それぞれの要素 v1 に対して result = op(result, v1) を計算します。

また、foldLeft メソッドは LinearSeqOptimized によってオーバーライドされており、List を扱うとき実際には以下の処理が行われます。

foldRight メソッド -Seq の要素を末尾から畳み込み演算する

foldRight メソッドは、foldLeft とは処理の順序が反対で、コレクションの末尾から順に畳み込み演算を行うメソッドです。

foldRight メソッドは、TraversableOnce[+A] で以下のように定義されています。引数として初期値 z: B、行いたい処理 op: (A, B) => B をとり、コレクションの末尾から畳み込み演算を行います。

また、foldRight メソッドは IterableLike および LinearSeqOptimized によってオーバーライドされており、List を扱うとき実際には以下の処理が行われます。

foldRight は再帰的に定義されていますが、末尾再帰ではありません。そのため、扱うリストが大きい場合にスタックオーバーフローを起こす可能性があります。

reduce メソッド - Seq の要素どうしを先頭から計算する

reduce メソッドは、コレクションの要素同士を先頭から順に演算するメソッドです。

reduce メソッドは、TraversableOnce[+A] で以下のように定義されています。その実装では、reduceLeft メソッドを呼び出しています。

reduceLeft メソッドの定義は以下のようになっています。

まず、reduceLeft の引数には行いたい処理 op: (B, A) => B を与えます。コレクションが空の場合は UnsupportedOperationException という例外が投げられます。

コレクションの各要素に foreach でアクセスし、それぞれに対して reducer 関数を実行します。

reducer 関数は、計算結果である acc をコレクションの先頭要素で初期化し、その後コレクションの各要素 x に対して acc = op(acc, x) とします。そして、全ての要素に対して reducer 関数を適用したあと、その計算結果 acc を返します。

reduceLeft と foldLeft との違いは、初期値の有無です。初期値がないため、コレクションが空の場合は例外が発生します。

また、reduceLeft メソッドは LinearSeqOptimized によってオーバーライドされており、List を扱うとき実際には以下の処理が行われます。

LinearSeqOptimized.reduceLeft は、初期値をコレクションの先頭の値として与え、foldLeft を実行しています。

おわりに

本記事では、以下のことを学びました。

  • 不変コレクションと可変コレクションの存在
  • コレクションクラスの階層構造
  • Seq の定義
  • Seq の各メソッドの定義

References

[1] scala.collection (2.12.x)
[2] 可変コレクションおよび不変コレクション | Collections | Scala Documentation
[3] Traversable トレイト
[4] Iterable トレイト
[5] 列トレイト Seq、IndexedSeq、および LinearSeq