【Scala】呼び出し元のコレクションと同じコレクションを返す拡張メソッドを追加する方法

##1. 新しいコレクションを返すメソッドの特徴
Scalaのコレクションメソッドの中でも､ `map` や `filter` のように「新しいコレクションを返す」メソッドには､「適用後のコレクションは呼び出し元のコレクションを引き継ぐ」という興味深い特徴があります。
これは言葉より実際に見た方が早いので、例を見てみます。
以下は、`List`, `Vector`, `TreeSet` のそれぞれのコレクションに対して `map` メソッドを適用したときの例です。

```scala
scala> List(1, 2, 3).map { _ * 2 }
val res0: List[Int] = List(2, 4, 6)

scala> Vector(1, 2, 3).map { _ * 2 }
val res1: scala.collection.immutable.Vector[Int] = Vector(2, 4, 6)

scala> TreeSet(1, 2, 3).map { _ * 2 }
val res2: scala.collection.immutable.TreeSet[Int] = TreeSet(2, 4, 6)
```

見ての通り、変換前が `List` なら変換後も `List` ですし、`Vector` なら `Vector` 、`TreeSet` なら `TreeSet` と、元の具象クラスと同じコレクションが返ってきます。
これは `map` だけでなく、`filter` や `collect` などコレクションを返すメソッドに共通の仕様です。

##2. 拡張メソッド自作の壁
 `map` や `filter` がそういった動きになっているのはわかりましたが､同じように動作する拡張メソッドを自作したい場合はどうすればいいのでしょうか？

ここでは例として、既存の `filter` メソッドと全く同じ動きをする予定の `myFilter` という拡張メソッドを自作してみます。
(車輪の再発明なので実用性はありませんが、検証用です)

ですがこの単純なメソッドですら、作ろうとすると少し困ったことになるのがわかります。

例えば、`myFilter` を下記のように定義するとします。
ここでは `implicit class` で拡張メソッドを定義しています｡
`implicit class` はトップレベルに定義できないため､適当に `MyOps` オブジェクト内に配置しました (本質ではありません)｡

```scala
object MyOps {
  implicit class IterableOps[A](val self: Iterable[A]) extends AnyVal {
    final def myFilter(p: A => Boolean): List[A] = {
      val buf = new ListBuffer[A]()
      for (e <- self) {
        if (p(e)) buf += e
      }

      buf.toList
    }
  }
}
```

しかしこの書き方の場合、元のコレクションの具象クラスに関わらず、戻り値のデータ型は `List` に固定されてしまいます。

```scala
scala> import MyOps._
import MyOps._

scala> List(1, 2, 3, 4).myFilter { _ % 2 == 0 }
val res0: List[Int] = List(2, 4)

scala> Vector(1, 2, 3, 4).myFilter { _ % 2 == 0 }
val res1: List[Int] = List(2, 4) // List以外から呼び出してもListになる
```

あるいは以下のように戻り値の型を `Iterable` にしてしまえば具象クラスの隠蔽こそできますが、それも単に隠蔽しただけで､実体は `List` のままです。

```scala
def myFilter(p: A => Boolean): Iterable[A] 
```

標準ライブラリの `filter` メソッドのように､`List` なら `List` 、`Vector` なら `Vector`を返す拡張メソッドは定義できないのでしょうか？

考えられる案として､以下のように具象クラスごとに同名メソッドをそれぞれ定義するという手法が挙げられます｡

```scala
object MyOps {
  implicit class ListOps[A](val self: List[A]) extends AnyVal {
    // List用
    final def myFilter(p: A => Boolean): List[A] = {
      val buf = List.newBuilder[A]
      for (e <- self) {
        if (p(e)) buf += e
      }

      buf.result()
    }
  }

  implicit class VectorOps[A](val self: Vector[A]) extends AnyVal {
    // Vector用
    final def myFilter(p: A => Boolean): Vector[A] = {
      val buf = Vector.newBuilder[A]
      for (e <- self) {
        if (p(e)) buf += e
      }

      buf.result()
    }
  }
}
```

とはいえ､流石にこの手法は採りたくありません｡
標準ライブラリでは最適化のために、 override などを使いこういった手法を採用しているケースもありますが､今回はもっと統一的なやり方でいきたいと思います｡
そのために使うのが､ `IsIterableOnce` および `BuildFrom` という2つの`trait`です｡


##3. IsIterableOnce とBuildFrom を使った拡張メソッドの定義
それでは､ `IsIterableOnce` と `BuildFrom` を使った拡張メソッドの定義方法を見ていきます｡

といっても､実は公式ドキュメントの [scala.collection.generic.IsIterableOnce](https://www.scala-lang.org/api/current/scala/collection/generic/IsIterableOnce.html) のページを見ると､まさに定義例がそのまま書いてあります｡

以下のコードはドキュメントからの抜粋です｡
ただ動作確認用に､ついでに `import` 文を補足し､ `MyOps` 内に配置しています｡

```scala
import scala.collection.BuildFrom
import scala.collection.generic.IsIterableOnce

object MyOps {
  class FilterMapImpl[Repr, I <: IsIterableOnce[Repr]](coll: Repr, it: I) {
    final def filterMap[B, That](f: it.A => Option[B])(
      implicit bf: BuildFrom[Repr, B, That]
    ): That = {
      val b = bf.newBuilder(coll)
      for(e <- it(coll).iterator) f(e) foreach (b +=)
      b.result()
    }
  }

  implicit def filterMap[Repr](coll: Repr)(
    implicit it: IsIterableOnce[Repr]
  ): FilterMapImpl[Repr, it.type] =
    new FilterMapImpl(coll, it)
}
```

ここでは `filterMap` という名前の拡張メソッドを定義しています｡

メソッド名が同じなので紛らわしいですが､拡張メソッドとして扱われるのは上の `FilterMapImpl` クラス内の `filterMap` メソッドです｡
下の `implicit def` な `filterMap` メソッドは､呼び出し元のコレクションを `FilterMapImpl` クラスのインスタンスに暗黙変換するためのメソッドです｡

なお特に拡張メソッド側と名前を合わせる必要はないので､下の `filterMap` メソッドは別の名前でも構いません｡

拡張メソッドを `implicit class` ではなく `implicit conversion` で定義するという意味では､ これはScala 2.9 以前の拡張メソッドの定義方法とも言えます｡

上記のコードを実際に動かしてみると､まさに標準ライブラリの `map` や `filter` のように､呼び出し元の具象クラスと同じコレクションが返ってきます。

```scala
scala> import MyOps._
import MyOps._

scala> List(1, 2, 3, 4, 5).filterMap (i => if(i % 2 == 0) Some(i) else None)
val res0: List[Int] = List(2, 4)

scala> Vector(1, 2, 3, 4, 5).filterMap (i => if(i % 2 == 0) Some(i) else None)
val res1: scala.collection.immutable.Vector[Int] = Vector(2, 4)

scala> TreeSet(1, 2, 3, 4, 5).filterMap (i => if(i % 2 == 0) Some(i) else None)
val res2: scala.collection.immutable.TreeSet[Int] = TreeSet(2, 4)
```

素敵ですね｡
書き方はわかったので､次は `myFilter` も同様に実装してみます｡

##4. myFilter メソッドの定義
まずは上記のコードをそのままコピペし､必要な部分のみ変えてみます｡

```scala
import scala.collection.BuildFrom
import scala.collection.generic.IsIterableOnce

object MyOps {
  class MyFilterImpl[Repr, I <: IsIterableOnce[Repr]](coll: Repr, it: I) {
    final def myFilter[That](p: it.A => Boolean)(implicit bf: BuildFrom[Repr, it.A, That]): That = {
      val b = bf.newBuilder(coll)
      for (e <- it(coll).iterator) if (p(e)) b += e

      b.result()
    }
  }

  implicit def myFilter[Repr](coll: Repr)(implicit it: IsIterableOnce[Repr]): MyFilterImpl[Repr, it.type] =
    new MyFilterImpl(coll, it)
}
```

動かしてみると､きちんと呼び出し元と同じコレクションが返ってきます。

```scala
scala> import MyOps._
import MyOps._

scala> List(1, 2, 3, 4).myFilter { _ % 2 == 0 }
val res0: List[Int] = List(2, 4)

scala> Vector(1, 2, 3, 4).myFilter { _ % 2 == 0 }
val res1: scala.collection.immutable.Vector[Int] = Vector(2, 4)

scala> TreeSet(1, 2, 3, 4).myFilter { _ % 2 == 0 }
val res2: scala.collection.immutable.TreeSet[Int] = TreeSet(2, 4)
```

当初の目的が達成できたので､めでたしめでたし...ではあるのですが､流石にこれで終わるのも芸がないので､もう少し中身を掘り下げてみましょう｡

ソース内の型注釈をもう少し補足し､ついでに暗黙変換側のメソッド名を「変換しているのだ」とわかりやすいよう改名します｡

```scala
import scala.collection.{BuildFrom, mutable}
import scala.collection.generic.IsIterableOnce

object MyOps {
  class MyFilterImpl[Repr, I <: IsIterableOnce[Repr]](coll: Repr, it: I) {
    final def myFilter[That](p: it.A => Boolean)(implicit bf: BuildFrom[Repr, it.A, That]): That = {
      val xs: IterableOnce[it.A] = it(coll)
      val b: mutable.Builder[it.A, That] = bf.newBuilder(coll)
      for (e <- xs.iterator) {
        if (p(e)) b += e
      }

      b.result()
    }
  }

  implicit def convertToMyFilter[Repr](coll: Repr)(implicit it: IsIterableOnce[Repr]): MyFilterImpl[Repr, it.type] =
    new MyFilterImpl(coll, it)
}
```

この状態で､いくつか解説していきます｡

### IsIterableOnce トレイトの解説

まず､ `MyFilterImpl` クラスのコンストラクタに渡された引数 `it` は､`scala.collection.generic.IsIterableOnce[Repr]` を上限境界とした型のインスタンスです｡

```scala
class MyFilterImpl[Repr, I <: IsIterableOnce[Repr]](coll: Repr, it: I) 
```

この `IsIterableOnce`トレイトの中身を見てましょう｡

```IsIterableOnce.scala
trait IsIterableOnce[Repr] {

  /** The type of elements we can traverse over (e.g. `Int`). */
  type A

  @deprecated("'conversion' is now a method named 'apply'", "2.13.0")
  val conversion: Repr => IterableOnce[A] = apply(_)

  /** A conversion from the representation type `Repr` to a `IterableOnce[A]`. */
  def apply(coll: Repr): IterableOnce[A]
}
```

見ての通り `IsIterableOnce`トレイトは以下の2つの要素から成り立っています ( `conversion` は deprecated なので割愛します)｡

- 抽象型メンバ `A`
- 型引数 `Repr` から `IterableOnce[A]` を生成するためのメソッド `apply` 

抽象型メンバ `A` は､ざっくり言うとコレクション内の要素の型を表します｡

また `apply` メソッドを通じて､ `Repr` から `IterableOnce[A]` 型の値を生成できるように実装する必要があります｡

`MyFilterImpl` クラスに話を戻すと､こちらにも同じ名前の型引数 `Repr` があります｡

```scala
class MyFilterImpl[Repr, I <: IsIterableOnce[Repr]](coll: Repr, it: I) 
```

そしてコンストラクタでは､この `Repr` 型の引数 `coll` と一緒に､ `IsIterableOnce[Repr]` 型の引数 `it` も渡してあげる必要があります｡

つまり､ `Repr` と `IsIterableOnce[Repr]` が揃ったということになります｡
そのため､ `it` の `apply` メソッドを使えば､ `coll` から `IterableOnce[it.A]` 型の値を生成できます｡
それが下の行でやっていることです｡

```scala
val xs: IterableOnce[it.A] = it(coll) // it.apply(coll) と同義
```

ここでは呼び出し時の `apply` を省略しています｡

具体的な実装は後述しますが､実は今回の `myFilter` は `coll` の型､つまり `Repr` 自体が `IterableOnce[it.A]` でもあるので､ここの `coll` と `xs` は実装上は全く同じものを指すようになっています｡
しかし `Repr` 自体には `IterableOnce` を上限境界とするような制約も､内部の要素の型についての情報もありません｡
そのため､ コンパイラに `IterableOnce[it.A]` という型を推論させるために､一旦 `IsIterableOnce[Repr]` を通しているわけです｡ [^1]

さて､これで `IterbleOnce[it.A]` が手に入ったので、 `for` や 
 `while` などでコレクションを走査することができるようになりました。
単に走査するだけでなく、走査しつつ新しいコレクションを作るのが今回の目的です｡
そのために､次の `BuildFrom` トレイトの機能を活用します。

### BuildFrom トレイトの解説
`myFilter` メソッドは､暗黙の引数に `scala.collection.BuildFrom` トレイトのインスタンスを要求します.

```scala
def myFilter[That](p: it.A => Boolean)(implicit bf: BuildFrom[Repr, it.A, That]): That
```

`BuildFrom` トレイトは、以下のように3つの型引数を取るトレイトです｡

```scala
trait BuildFrom[-From, -A, +C] extends Any
```

型引数の名前が変わっているので分かりづらい部分もありますが､ `myFilter` に照らし合わせると､ `From` が `Repr`､ `A` は `it.A`､ `C` は `That` になります｡
それが暗黙の引数 `bf` の型です｡

```scala
(implicit bf: BuildFrom[Repr, it.A, That])
```

`BuildFrom` トレイトは `newBuilder` という､ `From` から､  `scala.collection.mutable.Builder[A, C]` 型の値を生成するメソッドを定義しています｡

```BuildFrom.scala
def newBuilder(from: From): Builder[A, C]
```

`Builder` についての詳細な説明は割愛しますが､具体的なサブクラスの例としては､ `mutable.ListBuffer` や `mutable.StringBuilder` などが挙げられます｡
これらのクラスは内部の要素を追加・変更しながら､最後に `result` メソッドで最終的な値を生成する想定で作られています｡
例えば `ListBuffer[A]` なら最後に生成する値の型は `immutable.List[A]` ですし､ `StringBuilder` なら `String` です｡

<br>

そして､ここが今回の記事の肝となる部分なのですが､ `myFilter` メソッドは呼び出し元のコレクション `coll` を `bf` の `newBuilder` メソッドに渡し､「同じコレクションを生成するためのビルダー」を取得します｡[^2]


```scala
val b: mutable.Builder[it.A, That] = bf.newBuilder(coll)
```

Scala 2.13.5 の内部実装を元に具体例を挙げると､例えば呼び出し元のコレクションが `List` なら `ListBuffer` になりますし､ `Vector` なら `VectorBuilder` が返ってきます｡

あとは取得したビルダーに対して `+=` メソッドなどで要素の追加・変更をしながら､最後に `result` メソッドを呼び出すことで､呼び出し元のコレクションと同じコレクションを返す機能を実現しているわけです｡

### convertToMyFilter メソッドについて

`myFilter` メソッドがどういう動きをしているのかはわかりました｡
しかし実際には `myFilter` を呼び出す前に､ `convertToMyFilter` メソッドでコレクションを `MyFilterImpl` に暗黙変換するフェーズが存在します｡
こちらについても少し見てみましょう｡ 

```scala
implicit def convertToMyFilter[Repr](coll: Repr)(
  implicit it: IsIterableOnce[Repr]
): MyFilterImpl[Repr, it.type] = 
  new MyFilterImpl(coll, it)
```

そもそも､このメソッドは必要なのでしょうか？
Scala 2.10 以降､拡張メソッドは `implicit class` を使って表現することがほとんどです｡
例えば `MyFilterImpl` クラスも､以下のように `implicit class` として定義し､ `convertToMyFilter` メソッドを削除することはできないのでしょうか？

```scala
implicit class MyFilterImpl[Repr, I <: IsIterableOnce[Repr]](coll: Repr)(implicit it: I)
```

結論から言うと､できません｡

詳細は割愛しますが､ `Repr` などの総称型や､ `convertToMyFilter` メソッドの戻り値の型である `MyFilterImpl[Repr, it.type]` の `it.type` の部分の兼ね合いもあり､先にこのメソッドを経由しておかないと型推論がうまく効きません｡
興味のある方は試してみてください (もしうまくいったら教えてください)｡

暗黙変換 ( `implicit conversion` ) は混乱を生みやすいため現在では使用を控える傾向にありますが､今回のケースに関しては `filterMap` で見たように､公式のScalaDocに例として記載されていることもあり､許容してもいいと考えています｡


###おまけ ～暗黙の引数に渡されているもの ( Vetor[Int] の場合)～
解説は以上なのですが､ `filterMap` にしろ `myFilter` にしろ､ `IsIterableOnce` と `BuildFrom` 型の暗黙引数をどこからか渡しています｡
これらの実体は呼び出し元によって変わるとはいえ､必ずどこかに定義自体はされているはずです｡

下記は `Vector[Int]` 型のコレクションに対し `myFilter` メソッドを呼び出す際に､全ての暗黙な部分を明示的にし､型注釈もガチガチにつけたものです｡
単なる一例ではありますが､どこからどういった値が渡され､推論されているのかを理解する一助になれば幸いです｡

```scala
  val coll: Vector[Int] = Vector[Int](1, 2, 3, 4)

  val it: IsIterableOnce[Vector[Int]] { type A = Int } =
    IsIterableOnce.iterableOnceIsIterableOnce[Vector, Int]

  val myFilterImpl: MyFilterImpl[Vector[Int], it.type] =
    convertToMyFilter[Vector[Int]](coll)(it)

  def bf[B]: BuildFrom[Vector[Int], B, Vector[B]] =
    BuildFrom.buildFromIterableOps[Vector, Int, B]

  val result: Vector[Int] =
    myFilterImpl.myFilter[Vector[Int]] { _ % 2 == 0 }(bf[Int])

  println(result)  // Vector(2, 4)
```

##おわりに
コレクションの拡張メソッドを作ろうとした際､呼び出し元のコレクションと同じコレクションを返す方法がわからず調べたり聞いたりしたところ､想像以上にややこしい仕組みが必要だと知って驚きました｡
ですがそれが「無理」ではなく「実現可能」だったのは､Scala の素晴らしい点の一つだと思います｡
今回の `myFilter` は機能的には実用性に欠けていたので､次は今回の知識をベースに､もう少し実用的な関数を定義してみたいと思います｡
<br>
最後までお読み頂きありがとうございました｡
質問や不備についてはコメント欄か[Twitter](https://twitter.com/ka2_kamaboko)までお願いします。

[^1]: 試しに `IsIterableOnce` を使わない方向で `MyFilterImpl` を実装しようとしてみると､ここで言っていることの理解が深まると思います｡
[^2]: コレクション内の要素の型は変わる可能性があります｡ `myFilter` は単なる `filter` なので変わりませんが､ `filterMap` の方は別の型に変換しています｡