Help understanding why type name is subject to erasure

Question
1

In the following function, I get a compiler warning that I don’t 100% understand.

  def treeReduce[A, B](objects: TraversableOnce[A], init: B, g: A => B, f: (B, B) => B): B = {
    def consumeStack(stack: List[(Int, B)]): List[(Int, B)] = {
      stack match {
        case (i, a1) :: (j, a2) :: tail if i == j => consumeStack((i + 1, f(a1, a2)) :: tail)
        case _ => stack
      }
    }

    val stack = objects.foldLeft((1, init) :: Nil) { case (stack: List[(Int, B)], ob: A) =>
      (1, g(ob)) :: consumeStack(stack)
    }
    // there may be up to log_2 of objs.size many pairs left on the stack
    assert(stack != Nil)

    stack.tail.map(_._2).foldLeft(stack.head._2)(f)
  }

The warning is:

Warning:(419, 84) abstract type pattern A is unchecked since it is eliminated by erasure
    val stack = objs.foldLeft((1, init) :: Nil) { case (stack: List[(Int, B)], ob: A) =>

I don’t understand what it is that is not being checked? Is it saying it doesn’t know whether ob is of type A. In my mind ob is guaranteed to be of type A because objects is Traversable[A], so foldLeft promises that this second argument has type A.

Or is the compiler telling me that it does not know whether objects is really of type Traversable[A]?

Or is the problem elsewhere?

2

You use case in your function passed to foldLeft here, which creates a partial function using a pattern match. As a pattern match is checked at runtime, the type A will be erased (i.e. the pattern match would not be able to check, if ob really is of type A).

But here the solution is simple: foldLeft expects a function accepting two parameters, not a tuple of them. So the pattern matching is not necessary and simply removing the case keyword should fix the problem.

1 Like
3

Thanks for pointing that out to me. For the past 6 months I’ve been thinking that foldLeft takes a function mapping a tuple to a value, and the compiler seems to be ok with my misguided assumption. I suspect I now have a big backlog fold call-sites where I need to remove a destructuring pattern match.

BTW, this is one thing which I accept, but don’t really like, that Scala seems to conflate pattern matching with destructuring lambda lists, apparently because their implementation is the same at the low level. But from the programmer’s perspective they seem different.

4

Why? The signature is

def foldLeft[B](z: B)(op: (B, A) => B): B

…where (B, A) => B is sugar for Function2[B, A, B].

It isn’t.

val fTwoArgs: Function2[Int, Int, Int] = ???
Seq(1, 2, 3).foldLeft(0)(fTwoArgs) // ok

val fTuple: Function[(Int, Int), Int] = ???
Seq(1, 2, 3).foldLeft(0)(fTuple) // doesn't compile

I’m not even sure what that means, and I’m not 100% confident I understand the interop of the Scala mechanism at work here, but I think it’s not what you think it is. :slight_smile:

My interpretation is this:

  • Partial Functions are expressed using pattern matching.
  • PartialFunction[A, B] extends Function[A, B] (yes, that’s fishy). So you can use a partial function instance where a (total) function is required.
  • For partial functions, there’s some kind of auto-tupling going on - a partial function literal(?!) representing a PartialFunction[(B, A), A] can be used to define a Function[B, A, A].

(The last part is shaky ground for me - a (very quick) web search didn’t bring up a concise description of this specific application of auto-tupling, but some discussions that leave the impression that auto-tupling is not that particularly well-defined and universally loved in general.)

Putting all of these together, you can define

val fTwoArgs: Function2[Int, Int, Int] = {
  case (a, b) => a + b
}

…and this also works with type parameters thrown into the mix:

class Foo[A : Numeric](as: Seq[A]) {
  as.foldLeft(0) { case (a, c) => a + implicitly[Numeric[A]].toInt(c) }
}

However, if you add explicit type declarations…

class Foo[A : Numeric](as: Seq[A]) {
  as.foldLeft(0) { case (a: Int, c: A) => a + implicitly[Numeric[A]].toInt(c) }
}

…the compiler will not see this as a confirmation hint of the types it derives, but rather as an additional constraint on the match, and will dutifully inform you that it will lose track of the concrete type for A at runtime, just as it will for any other pattern match involving type parameters.

5

Here is the code I usually type, which compiles. That’s why I was calling it misguided. I think it is ultimately wrong, but the compiler fixes my errors for me. So for a while now, I thought this was normal. Thanks for pointing out that it is not.

List(1,2,3,4).foldLeft(0){case (acc:Int, i:Int) => acc + i}
6

The problem here is not really that the compiler fixes an error automatically, because using case here is valid. It’s just not required in your use case. Your code translates to:

(acc: Int, i: Int) => (acc,i) match { case (acc:Int, i:Int) => acc + i}

as the expected type here is (Int,Int) => Int.

The syntax is basically a shortcut for a function, that only matches on all of its inputs anyway. It is useful even for functions that do not need to destructure tuples, because you actually can have several cases in such a literal. See the spec for the translation rules. So if you would only do a match on all parameters anyway, you can leave off the extra parameter list.

A PartialFunction is only created, if one is expected in that position, but its translation is similar, it just adds the isDefinedAt method (and some optimizations to prevent repeated pattern matches).

7

What I meant is that the compiler isn’t ok with your assumption. :slight_smile:

It’s not wrong/an error - it’s just the compiler interpreting a tupled partial function literal as a two-argument (total) function (auto-tupling and partial function is-a total function as parts of this interpretation certainly not being terribly intuitive). But the type of the function needs to be right once it hits the #foldLeft().

val partFunTupled: PartialFunction[(Int, Int), Int] =
  { case (acc:Int, i:Int) => acc + i }
List(1,2,3,4).foldLeft(0)(partFunTupled) // doesn't compile

val funTupled: Function[(Int, Int), Int] =
  { case (acc:Int, i:Int) => acc + i }
List(1,2,3,4).foldLeft(0)(funTupled) // doesn't compile

val funTwoArgs: Function2[Int, Int, Int] =
  { case (acc:Int, i:Int) => acc + i }
List(1,2,3,4).foldLeft(0)(funTwoArgs) // ok

It’s not exactly “normal”, but a rather convoluted way of defining a total two-parameter function. Just use a plain lambda/function/method reference, unless you really want to destructure the arguments with a pattern match.