Scala で Seq や Map 等の Traversable なコレクションについてのジェネリックなメソッド書きたくないですか

小ネタです。みなさん Scala でジェネリックなメソッド、便利なので書いてますよね。そこでコレクションについてのジェネリックなメソッドも書きたくなってきます。

```scala
def myMap[T, U, A[T] <: Traversable[T]](a: A[T])(f: T => U): A[U] = a.map(f)
```

まぁこれは冗談にしても、たとえばコレクションを型引数としてとって、返り値をそのコレクションで包んで返したいなんてのはあるんじゃないかと思います。

```scala
val hoge: List[Result] = piyo.get[List] // def get[A[_]]: A[Result] = ???
```

しかし、上記のコードはコンパイル通りません。

結論から言うと、下記のようにするとコレクションについてジェネリックなメソッドを定義できます。

```scala
def myMap[T, U, A[T] <: TraversableLike[T, A[T]]](a: A[T])(f: T => U)(implicit cbf: CanBuildFrom[A[T], U, A[U]]): A[U] = a.map(f)
```

もうこれで答えなので、どうしてこれでうまくいくのか興味がない人はこれでおしまいです。お疲れ様でした。

# 理由

まぁ理由気になりますよね！使いこなすためにも。
Scala の REPL で改善しながら上記の答えにたどり着いてみましょう。まずは最初の状態。

```scala
scala> def myMap[T, U, A[T] <: Traversable[T]](a: A[T])(f: T => U): A[U] = a.map(f)
<console>:13: error: type mismatch;
 found   : Traversable[U]
 required: A[U]
       def myMap2[T, U, A[T] <: Traversable[T]](a: A[T])(f: T => U): A[U] = a.map(f)
                                                                                 ^
```

Traversable は Traversable を返す実装になっていてジェネリックになっていないようです(そりゃそうだ)。こまった。

しかし Scala の標準ライブラリはちゃんと考えてくれていました。Traversable のサブクラスを実装するための TraversableLike というトレイトが用意してあります。これを使いましょう。これであるコレクション A という型パラメータを Traversable なやつに渡すことができます。

```scala
scala> def myMap[T, U, A[T] <: TraversableLike[T, A[T]]](a: A[T])(f: T => U): A[U] = a.map(f)
<console>:13: error: type mismatch;
 found   : scala.collection.TraversableOnce[U]
 required: A[U]
       def myMap[T, U, A[T] <: TraversableLike[T, A[T]]](a: A[T])(f: T => U): A[U] = a.map(f)
                                                                                          ^
```

今度は TraversableOnce が返されて型があいません。TraversableLike にちゃんと A[T] 渡してるのに...

わからないので、Traversable な既存のコレクションではどうなってるのか見てみます。[List.scala](https://github.com/scala/scala/blob/v2.11.8/src/library/scala/collection/immutable/List.scala#L270) で map を見てみると

```scala
final override def map[B, That](f: A => B)(implicit bf: CanBuildFrom[List[A], B, That]): That
```

なんと implicit パラメータがいます。CanBuildFrom[List[A], B, That] というものすごい怪しいやつがいますね。明らかに List[A] を B について戻り型の That に変えてそうです。ということは、こいつを渡してやればいいのでは...？

```scala
scala> def myMap[T, U, A[T] <: TraversableLike[T, A[T]]](a: A[T])(f: T => U)(implicit cbf: CanBuildFrom[A[T], U, A[U]]): A[U] = a.map(f)
warning: there was one feature warning; re-run with -feature for details
myMap: [T, U, A[T] <: scala.collection.TraversableLike[T,A[T]]](a: A[T])(f: T => U)(implicit cbf: scala.collection.generic.CanBuildFrom[A[T],U,A[U]])A[U]
```

はいできました！最終形が完成しましたね。

# CanBuildFrom とは

CanBuildFrom の Scaladoc をみると、A base trait for builder factories. と書いてあります。どうやらコレクションの Builder に関係があるようです。

# CanBuildFrom はどこからくるのか

通常、コレクションメソッドを使うときに implicit な CanBuildFrom について意識することはありません。どっかで誰かが implicit に生やしているはずです。

先程と同様に [List.scala](https://github.com/scala/scala/blob/v2.11.8/src/library/scala/collection/immutable/List.scala) を見てみます。74行目あたりを見ると

```
 *  @define bfinfo an implicit value of class `CanBuildFrom` which determines the
 *    result class `That` from the current representation type `Repr`
 *    and the new element type `B`. This is usually the `canBuildFrom` value
 *    defined in object `List`.
```

ということで、どうやら List の object に CanBuildFrom の値について定義があるようです。これまた見に行くと

```scala
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, List[A]] =
  ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]
```

ということで、コレクションクラスの object に CanBuildFrom の implicit な値が生えているようです。コレクションメソッドを呼び出すときに CanBuildFrom を意識しなくていい謎が解けました。

ということで、Scala で Traversable なコレクションについてジェネリックなメソッドを書く方法とその理由でした。めでたしめでたし。