We recently had an internal knowledge sharing on higher-kinded types and `CanBuildFrom` type classes in Scala. Here’s a short summary.

## Basics

Let’s start by implementing `map`.

``````def map(xs: Seq[Int], f: Int => Double): Seq[Double] = xs.map(f)
map(Seq(1, 2, 3), _ + 0.1)
``````

This implementation is not very good since it only works with `Seq[Int]` and `Int => Double`. It’s easy to parameterize `Int` and `Double`.

``````def map[A, B](xs: Seq[A], f: A => B): Seq[B] = xs.map(f)
``````

However `map(Seq(1, 2, 3), _ + 0.1)` now fails to compile with a message `missing parameter type for expanded function ((x\$1) => x\$1.\$plus(10))`

This is because inference of `A` in `f: A => B` depends on the type of `xs: Seq[A]`, and limitation of Scala type inference. A common workaround is to curry arguments.

``````def map[A, B](xs: Seq[A])(f: A => B): Seq[B] = xs.map(f)
map(Seq(1, 2, 3))(_ + 0.1)
``````

Similar pattern is commonly seen in Scala, like `foldLeft(z: B)(op: (B, A) => B)`. Another benefit is we can now write `f` in a multi-line `{}` block more elegantly.

``````map(Seq(1, 2, 3)) { x =>
val y = x + 0.1
println(s"\$x + 0.5 = \$y")
y
}
``````

## Higher-kinded types

However this version still only works on `Seq[A]`. We could parameterize it as `M[_]`, also known as higher-kinded type.

``````import scala.language.higherKinds
def map[M[_], A, B](xs: M[A])(f: A => B): M[B] = xs.map(f)
``````

But now we have a compiler error saying `value map is not a member of type parameter M[A]`. We can add a upper bound for `M[_]` but it still wouldn’t work.

``````def map[M[_] <: Seq[A], A, B](xs: M[A])(f: A => B): M[B] = xs.map(f)
``````

Despite the fact that `M[_]` is a sub-type of `Seq[A]`, and `Seq[A]` has a `map` method, we can’t build a `M[B]` back from `Seq[A]#map[B](f: A => B)`, since `M[B]` is a more specific type than `Seq[B]`.

``````type mismatch;
[error]  found   : Seq[B]
[error]  required: M[B]
``````

However if we look at the method signature of `Seq[A]#map(f: A => B)` it actually looks like this.

``````trait TraversableLike[+A, +Repr] {
def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That
}
``````

Note that it’s a method on `trait TraversableLike`, which means any `TraversableLike` collection can share the same `map` implementation. Also worth noting is `Seq[+A]` has an inheritance hierarchy like this:

``````trait Seq[+A] extends SeqLike[A, Seq[A]] // ...
trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] // ...
trait IterableLike[+A, +Repr] extends TraversableLike[A, Repr] // ...
``````

We see that in `Seq[A] extends SeqLike[A, Seq[A]]`, type of the current trait `Seq[A]` is also used as a type parameter for the super-type, which is propagated all the way to `TraversableLike`. This is commonly known as F-bounded polymorphism, which is useful heere since methods on sub-types of `TraversableLike` can now return a more specific type, e.g. `Seq`, `List`, `Vector`, instead of the same broad super-type. For more information on F-bounded polymorphism, check out Marconi Lanna’s excellent presentation at NEScala 2015.

In the case of `Seq[Int]#map(f: Int => Double)`, we can expand the method like this:

``````def map[Int, That](f: Int => Double)(implicit bf: CanBuildFrom[Seq[Int], Double, That])
``````

## CanBuildFrom

`CanBuildFrom` is a key type class in the Scala collections library and enables a lot code reuse.

``````trait CanBuildFrom[-From, -Elem, +To]
``````

In its type signature, `From` is the original collection and `To` is the target collection. `Elem` is the element type of the target collection and in some determines the type of `To`. For example we can map over a `Map[K, V]` into `K -> V` (which is a syntactic sugar for `(K, V)`), and get another map. However mapping into `String` would result in a `List[String]` since one cannot build a `Map[K, V]` with a single type.

``````// From: Map[String, Int]
// (String, Int) => (String, Double)
// To: Map[String, Double]
// CanBuildFrom[Map[String, Int], (String, Double), Map[String, Double]]
Map("a" -> 1, "b" -> 2).map(kv => kv._1 -> kv._2 + 0.1)

// From: Map[String, Int]
// (String, Int) => String
// To: List[String]
// CanBuildFrom[Map[String, Int], String, List[String]]
Map("a" -> 1, "b" -> 2).map(kv => kv._1 + kv._2.toString)
``````

We can use `CanBuildFrom` to rewrite our `map` function.

``````def map[M[_] <: Seq[A], A, B](xs: M[A])(f: A => B)
(implicit cbf: CanBuildFrom[M[A], B, M[B]]): M[B] = {
val b = cbf() // new Builder[Elem, To]
xs.foreach(x => b += f(x))
b.result()
}
``````

Our function can now support any `Seq` types without losing the type information.