title: Working with scala collections - CanBuildFrom trouble
body: <p>I'm trying to write a method which accepts any type of collection <code>CC[_]</code> and maps it to a new collection (the same collection type but a different element type) and I am struggling royally. Basically I'm trying to implement <code>map</code> but <em>not on the collection itself</em>.</p>
  
  <h2>The Question</h2>
  
  <p>I'm trying to implement a method with a signature which looks a bit like:</p>
  
  <pre><code>def map[CC[_], T, U](cct: CC[T], f: T =&gt; U): CC[U]
  </code></pre>
  
  <p>It's usage would be:</p>
  
  <pre><code>map(List(1, 2, 3, 4), (_ : Int).toString) //would return List[String]
  </code></pre>
  
  <p>I'm interested in an answer which would also work where <code>CC</code> is <code>Array</code> and I'm interested in the reason my attempts (below) have ultimately not worked.</p>
  
  <hr/>
  
  <h2>My Attempts</h2>
  
  <p><em>(For the impatient, in what follows, I utterly fail to get this to work. To reiterate, <strong>the question</strong> is "how can I write such a method?")</em></p>
  
  <p>I start like this:</p>
  
  <pre><code>scala&gt; def map[T, U, CC[_]](cct: CC[T], f: T =&gt; U)(implicit cbf: CanBuildFrom[CC[T], U, CC[U]]): CC[U] = 
       | cct map f
                                                               ^
   &lt;console&gt;:9: error: value map is not a member of type parameter CC[T]
         cct map f
             ^
  </code></pre>
  
  <p>OK, that makes sense - I need to say that <code>CC</code> is traversable!</p>
  
  <pre><code>scala&gt; def map[T, U, X, CC[X] &lt;: Traversable[X]](cct: CC[T], f: T =&gt; U)(implicit cbf: CanBuildFrom[CC[T], U, CC[U]]): CC[U] = 
       | cct map f
  &lt;console&gt;:10: error: type mismatch;
   found   : Traversable[U]
   required: CC[U]
         cct map f
             ^
  </code></pre>
  
  <p>Err, OK! Maybe if I actually specify that <code>cbf</code> instance. After all, it specifies the return type (<code>To</code>) as <code>CC[U]</code>:</p>
  
  <pre><code>scala&gt; def map[T, U, X, CC[X] &lt;: Traversable[X]](cct: CC[T], f: T =&gt; U)(implicit cbf: CanBuildFrom[CC[T], U, CC[U]]): CC[U] = 
       | cct.map(t =&gt; f(t))(cbf)
  &lt;console&gt;:10: error: type mismatch;
   found   : scala.collection.generic.CanBuildFrom[CC[T],U,CC[U]]
   required: scala.collection.generic.CanBuildFrom[Traversable[T],U,CC[U]]
         cct.map(t =&gt; f(t))(cbf)
                            ^
  </code></pre>
  
  <p>Err, OK! That's a more specific error. Looks like I can use that!</p>
  
  <pre><code>scala&gt; def map[T, U, X, CC[X] &lt;: Traversable[X]](cct: CC[T], f: T =&gt; U)(implicit cbf: CanBuildFrom[Traversable[T], U, CC[U]]): CC[U] = 
       | cct.map(t =&gt; f(t))(cbf)
  map: [T, U, X, CC[X] &lt;: Traversable[X]](cct: CC[T], f: T =&gt; U)(implicit cbf: scala.collection.generic.CanBuildFrom[Traversable[T],U,CC[U]])CC[U]
  </code></pre>
  
  <p>Brilliant. I has me a <code>map</code>! Let's use this thing!</p>
  
  <pre><code>scala&gt; map(List(1, 2, 3, 4), (_ : Int).toString)
  &lt;console&gt;:11: error: Cannot construct a collection of type List[java.lang.String] with elements of type java.lang.String based on a collection of type Traversable[Int].
                map(List(1, 2, 3, 4), (_ : Int).toString)
                   ^
  </code></pre>
  
  <p>Say, what?</p>
  
  <hr/>
  
  <h2>Observations</h2>
  
  <p><em>I really can't help but think that Tony Morris' observations about this at the time were absolutely spot on. What did he say? He said "<strong>Whatever that is, it is not map</strong>". Look at how easy this is in scalaz-style</em>:</p>
  
  <pre><code>scala&gt; trait Functor[F[_]] { def fmap[A, B](fa: F[A])(f: A =&gt; B): F[B] }
  defined trait Functor
  
  scala&gt; def map[F[_]: Functor, A, B](fa: F[A], f: A =&gt; B): F[B] = implicitly[Functor[F]].fmap(fa)(f)
  map: [F[_], A, B](fa: F[A], f: A =&gt; B)(implicit evidence$1: Functor[F])F[B]
  </code></pre>
  
  <p><em>Then</em></p>
  
  <pre><code>scala&gt; map(List(1, 2, 3, 4), (_ : Int).toString)
  &lt;console&gt;:12: error: could not find implicit value for evidence parameter of type Functor[List]
                map(List(1, 2, 3, 4), (_ : Int).toString)
                   ^
  </code></pre>
  
  <p><em>So that</em></p>
  
  <pre><code>scala&gt; implicit val ListFunctor = new Functor[List] { def fmap[A, B](fa: List[A])(f: A =&gt; B) = fa map f }
  ListFunctor: java.lang.Object with Functor[List] = $anon$1@4395cbcb
  
  scala&gt; map(List(1, 2, 3, 4), (_ : Int).toString)
  res5: List[java.lang.String] = List(1, 2, 3, 4)
  </code></pre>
  
  <p>Memo to self: <strong>listen to Tony!</strong></p>