Scala 2.13 のコレクションライブラリの設計について

## はじめに
Scala (v2.12) のコレクションのクラス構造が謎だなとはわりと思っていて（`Xxx` と `XxxLike` と `GenXxx` ってなに〜）、[The Architecture of Scala Collections](https://docs.scala-lang.org/overviews/core/architecture-of-scala-collections.html) あたりを読んでまとめようと思っていました。
しかし、v2.13 でコレクションに入る（正確に言うと、 2.13.0-M4 で入った）変更をドキュメントやソース読みつつ調べていたら、ほんとうに大きな変更だなあ、なんだかここでまとめてももったいないなあ、という気持ちになってきたので 2.13 のコレクションについてざっくり調べてみることにしたのでした。

この記事では、scala-lang.org にある、コレクションライブラリの設計概念について書かれているドキュメントをざっくり訳しつつ 2.13 でのコレクションの設計などについて理解を深めようと思います。

## TL; DR
2.13 でのコレクションライブラリの設計や実際の変更について知りたいならこれらを読めばだいたいわかるんじゃないかと思います。

- [Scala 2.13 Collections Rework](https://www.scala-lang.org/blog/2017/02/28/collections-rework.html)
- [Release Scala 2.13.0-M4 · scala/scala](https://github.com/scala/scala/releases/tag/v2.13.0-M4) の "Collections changes"
- [FAQ · scala/collection-strawman Wiki](https://github.com/scala/collection-strawman/wiki/FAQ)


### 免責
- ドキュメントの意図を正しく表現できていることは保証しません
    - 誤り指摘は歓迎です


---
### LICENSE
The following document is Japanese translation of Stefan Zeiger's "Scala 2.13 Collections Rework" (https://www.scala-lang.org/blog/2017/02/28/collections-rework.html).

This document is licensed by @gion under a Creative Commons Attribution-Share Alike 3.0 Unported license ("CC-BY-SA").


## Scala 2.13 Collections Rework
2015年の10月に Odersky は Scala 2.13 向けの新しいコレクションライブラリの試案を求めた。
Scala のコレクションの再設計ははじめてのことではなく、現在の形のものは Scala 2.8 においてはじめて実装され、Scala コンパイラの型推論に必要な改良が加えられた。
現在のコレクションライブラリはおおむね共通のインターフェースとコードベースを持つ、可変・不変、直列・並列なコレクションを提供しており、基本的には成功しているといえる一方で、セカンドシステム症候群の兆候を示しているような部分もある。

### Goals
問題点や新しい設計での解決策の案を探す前に、新しい設計が目指すところから定義する:

- APIの単純化（利用者向き）: これには一般的な操作を `CanBuildFrom` なしで行うこと、継承ツリーを整理すること、可変コレクションと不変コレクションに対する操作のよりよい分離が含まれる
- APIの単純化（ライブラリ開発者向き）: いまのところ、新しいコレクション型の実装は自明からはほど遠く、望む型の `CanBuildFrom` のインスタンスが得られるように implicit なオブジェクトを用意するのは面倒。また、たくさんのデフォルト実装を継承できるのは利点に見える一方で、それが十分な性能を発揮するかは自分でチェックし、必要ならオーバーライドしないといけない
- よりよい性能のためのデザイン: 最高のアルゴリズムも、プリミティブ型に対する特殊化や JVM のメソッドディスパッチなどの低レイヤにおけるパフォーマンスへの懸念を無視してしまっては有用にならない。Slick のクエリコンパイラでは、Scala ライブラリのものではなく自前のコレクションを利用することで 25% の性能向上を果たした。一般化されたライブラリで同等の性能向上は達成できなくても、改善の余地があることは示されている
- 2.12 との高い互換性: コレクションの使い方の大部分は 2.12 と 2.13 の間で互換性を保ち、非互換な部分もおおむね ScalaFix で自動的に修正できるだろう

### Traversable and Iterable
現在のコレクションライブラリは、基本的に `Traversable` を継承ツリーのルートとしているが、これの実際のサブクラスは `Iterable` のみである。
両者の違いは、 `Traversable` が `foreach` として内部的イテレーションを提供するにとどまるのに対し、 `Iterable` が `Iterator` 型を通してより強力な外部的イテレーションを提供している。
`Traversable` での抽象化は現在のライブラリにおいては重要ではなく、また新設計においても表出することはないため、 `Iterable` があれば事足りる。

また、コレクションのトレイトを削除する他の機会も窺っている。それぞれのトレイトは妥当な理由があって存在してはいるが、その数とそれらの相互作用でライブラリの複雑度が高くなっている。たとえば、現在の `List` クラスの宣言について:

```scala
sealed abstract class List[+A] extends AbstractSeq[A]
                               with LinearSeq[A]
                               with Product
                               with GenericTraversableTemplate[A, List]
                               with LinearSeqOptimized[A, List[A]]
                               with scala.Serializable {
  ...
}
```
親タイプは全部で40個近くになる。

### CanBuildFrom
現在のコレクションライブラリの中で最も強力であり、一方で議論の余地にあるものの1つは `CanBuildFrom`  だ:

```scala
def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That
```
これは `TraversableLike`で宣言されている `map` メソッドのシグニチャだ。初心者にはこれは分かりにくいため、意図をより明確に伝える『ユースケースの』シグネチャがAPIドキュメントに追加された:

```scala
 def map[B](f: A => B): $Coll[B]
```
これによって Scaladoc 上ではわかりやすくなったものの、IDEでの補完やコンパイラのエラーでは依然として実際の定義と付き合う必要がある。
 
新設計では、 `map` メソッドは次のように宣言される:

```scala
def map[B](f: A => B): C[B]
```
このメソッドは期待されたシグネチャを持ち、正しい `CanBuildFrom`を探索するコンパイル時や実行時のオーバーヘッドもなく、また型コンストラクタ `C` はほとんどのユースケースで具象コレクション型となるように改善されているために、Scaladoc のみでなくコード補完やエラーメッセージ中でも期待されたシグネチャの形で見ることができる。

`CanBuildFrom` は Scala 2.8 で導入され、これによって制約のないコレクションと、要素の型に対する implicit evidence[^1] を必要とする制約付きコレクションの両方に対して `map` などの標準的なメソッドの定義を1度で済ますことができる。
たとえば、 `BitSet` は `class BitSet extends Set[Int]` と自然に定義できるだろうが、次のように `map` を呼ぶことは何を意味するだろうか:

```scala
val s: BitSet = ...
val c1 = s.map(i => i+1)
val c2 = s.map(i => i.toString)
```
現在の設計では `c1` として `BitSet` を、 `c2` として `HashSet` を実行時に構築するだけでなく、型推論をコンパイル時に行うこともできる。
一方で、次のようなコードになると、話は複雑になってくる:

```scala
val s: BitSet = ...
val c1 = (s: Set[Int]).map(i => i+1)
```
ここで `c1` が `BitSet` になるとは考えないだろうが、このときにも依然実態としては `BitSet` なのか、それとも既定の `Set` 実装が用いられるのだろうか。実際この場合は後者であるが、現在のライブラリにおいてはコンパイル時と実行時で `Builder` 型の探索の整合性がとれていないので、型か実装が予期しないものになる可能性がある[^2]。

先に見たように、新設計では `map` が implicit evidence をパラメータとしてとらないので、`BitSet`を `BitSet` として扱っていても `Set[Int]` として扱っていても、常に同じ実装を利用することが保証され、この場合は `Set` の実装が利用される。
コレクションの実装は、制約がない限り、（継承ツリーにおいて、スーパークラスと自身の間にいる）任意のコレクション型を返すことができる。
`BitSet.map` を呼び出して、別の制約付き `BitSet` を得るようにするには、 `map` メソッドをオーバーロードする必要がある:

```scala
class BitSet extends Set[Int] {
  //def map[B](f: Int => B): Set[B]  // 継承で得たもの

  def map(f: Int => Int): BitSet
}
```

Scala 2.12 における型推論の強化によって、オーバーロードしたメソッドをラムダ関数を引数にして呼ぶときに型アノテーションが不要になっている:

```scala
val s: BitSet = ...

// Scala 2.11 以下ではこう書かないといけない:
val c1 = s.map((i: Int) => i+1)

// 2.12 以降ではこれでよい:
val c2 = s.map(i => i+1)
```

`BitSet`は若干特殊なコレクション型であるが、要素型 `T` についての暗黙的な制約の原則は他のコレクション型にも適用される:
- BitSet: `T <:< Int` （『`Int` でなくてはならない』）
- 全ての `Map` 型: `T <:< (_, _)` （『`Tuple2` でなくてはならない』）
- 全ての Sorted なコレクション（`TreeSet` など）: `Ordering[T]` （『順序がなければならない』）
- String（それ自体はコレクションではないが、コレクションのメソッドを持つ）: `T <:< Char` （『`Char` でなくてはならない』）
- Array（String と同様にコレクションではないが）: `ClassTag[T]` （『型タグを持っていなくてはならない』）

ここで説明した設計では、 `CanBuildFrom` のほとんどの用途をはるかに簡単な方法で実現する。
新設計で直接サポートできない重要なユースケースに、 `collection.breakOut` （別のコレクション型を追加の変換ステップなしに直接作成する）と `to` （`CanBuildFrom`を使用できる別のコレクション型に変換する）があるが、同じ効果を達成するための代替方法を提供する。


### FromIterable
`to` メソッドは新設計でも依然存在するが、制約のない全てのコレクション型のコンパニオンオブジェクトによって実装されるメソッドの抽象である `FromIterable` のデコレータでしかない:

```scala
trait IterableOps[+A] extends Any {
  def to[C[X] <: Iterable[X]](fi: FromIterable[C]): C[A @uncheckedVariance] =
    fi.fromIterable(coll)
  ...
}

trait FromIterable[+C[X] <: Iterable[X]] {
  def fromIterable[B](it: Iterable[B]): C[B]
}
```
`fi` は（現在のライブラリの `CanBuildFrom` と違い）implicit でないため、型と一緒に呼び出して `CanBulidFrom` を探索するのではなく、値で呼び出して型を推論する:

```scala
val s: Set[Int] = ...
val v = s.to(Vector) // いままでは to[Vector]
```

この設計には `Map` やその他の制約つきコレクション型 `to` をオーバーロードできるという利点もある（現在のライブラリでは `to` は引数が1つの型コンストラクタにしか適用できない）。


### Views
現在のコレクションライブラリにおいて、ビューはライブラリ実装の複雑さを高めている割にあまり使われていない機能のひとつである。新設計では不変ビューと可変ビューを分離し（後者はまだ実装されていないが）。不変ビューはインデックスがあるかどうかで2つに分けることで、構造が大幅に簡潔化される。

概念的にはビューは Java 8 の `Stream` のように、新しい `View` を作成する中間操作（`filter` や `flatMap` など）と、 現在のViewで表わされている操作を `Iterator` に対して実行する終端操作（`foreach` や `foldLeft` など）を持つようになる。
これにより、中間操作によるビューの作成は基本となるコレクションの変化とは常に独立し、終端操作を呼び出すときだけコレクションの現在の状態が使用されるようになるため、可変コレクションに使用しても、明確なセマンティクスが得られる。

ビューは `collection.breakOut` の代替としても推奨される。たとえば、次の式:

```scala
val s: Seq[Int] = ...
val set: Set[String] = s.map(_.toString)(collection.breakOut)
```
は、同様のパフォーマンス特性を保ったまま、次のように書ける:

```scala
val s: Seq[Int] = ...
val set = s.view.map(_.toString).to(Set)
```
複数の操作を組み合わせた場合、実際の操作は遅延される:

```scala
val s: Seq[Int] = ...

// フィルタした Seq を作り、次にマップした Seq をつくり、Set にする
val set1 = s.filter(_ > 0).map(_.toString).to(Set)

// filter と map を同時に評価して Set を直接作る
val set2 = s.view.filter(_ > 0).map(_.toString).to(Set)
```

### Laziness
ビューとは別に、現在のコレクションライブラリは遅延コレクションもサポートしているものの、一級市民の扱いを受けない。
`Stream` は `tail` のみ遅延評価で `head` は正格評価され、また実装はほとんどの部分で自前の実装を必要とする。
なぜならば、新しいコレクションのインスタンスを構築するための基本抽象（正格コレクション型が安全に継承できるデフォルト実装）が、正格評価で push ベースでコレクションを構築する `CanBuildFrom` や `Builder` を用いているからだ。
`FromIterable` と新設計における `View` を組み合わせることで、コレクションの正格・遅延を問わず使える pull ベースの構築メソッドを提供することができる。実際、次に示すものが `map` の共通実装であり、遅延コレクションとするために `LazyList` でオーバーライドする必要はない[^3]:

```scala
def map[B](f: A => B): C[B] = fromIterable(View.Map(coll, f))
```
`View` に対する操作から現在のコレクション型を再構築できることに基いて、このような共通実装にまとめるができる。
`Iterator` を取得し、必要に応じて要素を1つずつ取り出すだけで、 `LazyList` を `Iterable` から『構築』することができるため、この共通実装から遅延評価する `map` の実装が自動的に得られる。


### Language Integration
`Predef` または `scala` パッケージオブジェクトのスコープにあるデフォルトの型の非対称性について疑問に思ったことがあるかもしれない:

```scala
scala> classOf[Set[_]]
res1: Class[Set[_]] = interface scala.collection.immutable.Set

scala> classOf[Map[_, _]]
res2: Class[Map[_, _]] = interface scala.collection.immutable.Map

scala> classOf[Seq[_]]
res3: Class[Seq[_]] = interface scala.collection.Seq
```
このように、`Seq` のみは不変コレクションではなく、可変シーケンスと不変シーケンスの両方を含むものになっている。
この理由は、Scala の言語仕様において、可変長引数を `scala.Seq` 型としているからだ（また、最上位である `scala` パッケージに含まれない型に依存したくないため）。
Java（および JVM）の可変長引数は実際に変更可能な配列なので、デフォルトの `Seq` は可変コレクションを許容する必要がある。
しかし実際には、このようなの配列は準不変として扱うことができるので、新設計に `ImmutableArray` ラッパーを追加して可変長引数に使用できるようにすることで、不変ではなくなっているデフォルトの `Seq` 型への依存を取り除くことを考えている。


### Outlook
（訳註: ドキュメントが書かれた当時、新コレクションライブラリが [github.com/scala/collection-strawman](https://github.com/scala/collection-strawman) で開発中であることや、今後の展望などが書いてある。情報が古いところもあるので省略）

---
（訳出ここまで）

## このドキュメントやほかのものを見ながらの所感とか
- 2.12 との互換性をとろうと頑張っているけれど、一部非互換になるところが出てくる
    - コレクション自作とかしている人はつらそう
- 2.13.0-M4 で scala/scala にマージされた
    - 既存のコレクション関連のトレイトも結構 deprecated になったりしている
- 並列コレクションが[別モジュールとして切り出される](https://github.com/scala/scala-parallel-collections)らしいが M4 に追いついてなさそうな雰囲気
- 結論として、利用者としては大変更を強いられることはあまりなさそうだしそこまで気に病まなくてもよさそう
    - ライブラリ開発者は……
- 2.13 と 2.12 のコレクション構造に多少明るくなれてよかった


## 今後の展望
- Scala のソースもう少し読みたい
- v2.13 実際に触る
- このコードがこう書き変えられる、というようなユーザー側からの違いも書いてみる



[^1]: この場合の evidence って訳したほうがいいのか、その場合ふつうどんな訳が当たるのか
[^2]: この段落を正しく訳せてる自信がない。とくに "still backed by" のくだり
[^3]: いまの 2.13.0-M4 では共通実装になっていない（ただし必要なものは実装されているようなので、たとえば `List` と `LazyList` で `def mapV[B](f: A => B): C[B] = fromIterable(new View.Map(coll, f))` などとしてあげれば期待の動作をしてくれそうな感じはある）。同一のコードベースでやるにはパフォーマンス等々で問題があったのかな？（未調査）