Type erasure in a nested list with a given context bound

Question

I am going through the book Scala with Cats. I am trying to understand the subtleties of the scala type system. I came up with the following example:

object Example extends App {

  sealed trait Serializer[T] {
    def serialize(seq: List[T]): String
  }

  implicit object StringSerializer extends Serializer[String] {
    def serialize(seq: List[String]): String = seq.toString()
  }

  implicit object IntSerializer extends Serializer[Int] {
    def serialize(seq: List[Int]): String =  seq.toString()
  }

  def f1[T0 : Serializer](x: List[List[T0]])(implicit s0: Serializer[T0]): List[String] = {
    x.map(lst => s0.serialize(lst))
  }
  
  // some dummy data
  val col1 = List("a", "b", "c", "d", "e")
  val col2 = List(12, 200, 80900, 201200, 124420000)
  val col3 = List(121, 12121, 71240000, 44356, 845)
  val data = List(col1, col2, col3)
  
  f1(data)
}

Now this does not compile, the following error comes up:

could not find implicit value for evidence parameter of type Example.Serializer[Any]

Now I understand why this happens; it is due to my function f1. Because I have a List[Int] and List[String] passed in to the function, the common parent type is Any. So the Type info gets erased, which passes into serializer.

However, given I have put a context bound, shouldn't the compiler first look for the implicit definitons before this takes place? Clearly it does not so my understanding is incorrect. What is the Scala way of getting round this problem.

Any explanations will be greatly appreciated!

Travis Brown Travis Brown · Accepted Answer · 2020-06-21T17:43:10

The issue is that the inferred type of data is List[List[Any]], so that when you call f1, the type that's inferred for T0 is Any, which doesn't have a Serializer instance. Even if you don't define data as a val, and instead write something like f1(List(col1, col2, col3)), the inferred type of T0 will still be Any.

Scala just doesn't really provide any way that you can do the kind of thing you're aiming for. The closest solution is probably something like the magnet pattern—for example you could add something like this:

trait SerializableList {
  type T
  def values: List[T]
  def instance: Serializer[T]
  final def apply(): String = instance.serialize(values)
}

object SerializableList {
  implicit def fromSerializer[T0](ts: List[T0])
    (implicit T: Serializer[T0]): SerializableList =
      new SerializableList {
        type T = T0
        val values = ts
        val instance = T
      }
}

And then define f1 like this:

def f1(x: List[SerializableList]): List[String] = {
  x.map(_())
}

And this actually works for your case, provided that you pass an expression where the element types haven't been inferred yet:

scala> f1(List(col1, col2, col3))
res3: List[String] = List(List(a, b, c, d, e), List(12, 200, 80900, 201200, 124420000), List(121, 12121, 71240000, 44356, 845))

But if you try f1(data) it still won't work, since the static type of data is already List[List[Any]]:

scala> f1(data)
          ^
       error: type mismatch;
        found   : List[List[Any]]
        required: List[SerializableList]

In my view it isn't really a good idea to use implicit conversions like this, anyway, though, even if they're powered by a type class.

As a footnote, what you're seeing doesn't really have anything to do with type erasure, which in Scala and Java is about losing access to generic types in runtime reflection. For example, this is an example of how type erasure can enable unsafe programs in Scala:

def broken() = List(1, 2, 3) match { case xs: List[String] => xs.head }

This compiles (with a warning), but crashes with a ClassCastException at runtime.

It's at least arguable that type erasure is a good thing, since unerased types undermine parametricity, and that the only problem in Scala is that its type erasure isn't more complete. The only issue with broken, in this view, is the ability to match on runtime type at all—not the fact that it doesn't work for generic types.

In your case there's no runtime reflection, and the fact that you've lost specific type information when Any is inferred isn't erasure, at least in the sense that term is typically used in this context. Instead it's a matter of the least upper bound being taken.

Type erasure in a nested list with a given context bound

1 Answers