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.

## Comments

comments powered by Disqus