Why collect with pattern match cannot narrow a specific class?

Question

Let's consider following trait:

sealed trait AB
case class A(a: Int) extends AB
case class B(b: Int) extends AB

I am trying to collect to limit a collection to specific subclass.

If I try to collect, matching individual components and reassembling the tuple:

scala> Seq.empty[(Int, AB)].collect { case (id, a @ A(_))  => (id, a) } : Seq[(Int, A)]
res6: Seq[(Int, ab.A)] = List()

compiler is happy, but if try to return a full match:

scala> Seq.empty[(Int, AB)].collect { case x @ (_, A(_))  => x } : Seq[(Int, A)]

things get ugly:

<console>:27: error: type mismatch;
 found   : Seq[(Int, ab.AB)]
 required: Seq[(Int, ab.A)]
       Seq.empty[(Int, AB)].collect { case x @ (_, A(_))  => x } : Seq[(Int, A)]

Why Scala compiler is unable to handle the second case?

Resourceful

Answer 1

It seems that this is because the pattern matching proceeds in top-down fashion into the subpatterns, without passing any additional information from the subpatterns to the root pattern.

When

x @ (_, A(_))

is matched, all x knows about the pattern is that it has the expected type (Int, AB), and this becomes the inferred type of x.

But when you attach pattern variables i and a to the subpatterns, then more specific information can be extracted and saved in the inferred types of i and a. In this particular case with a @ A(_), the following paragraph in the spec seems relevant:

A pattern binder x@p consists of a pattern variable x and a pattern p. The type of the variable x is the static type T of the pattern p.

In the case of A(_), the static type can be inferred to be A just by looking at the top-level element of the pattern, without recursing into subpatterns. Therefore, the type of a is inferred to be A, the type of id is inferred to be Int, hence (id, a) is inferred to have type (Int, A).

Chaqueta

The 2.13 has improved language. – Struggle

@Struggle Dotty also refuses to compile this; 2.13 on Scastie exited with some strange dependency resolution error. But yeah, would be nice if 2.13 inferred more, there is no reason why it should be impossible, it's just a bit more difficult to implement. – Chaqueta

Answer 2

The behavior is specified in Pattern Binders and Constructor Patterns.

It looks to me like this:

1. The expected type of the pattern is (Int, AB) (in both cases).

2. In case (id, a @ A(_)), the expected type of A(_) is AB, but the actual type is A.

3. In case x @ (_, A(_)), x's type is the type of pattern (_, A(_)). It's instantiated to Tuple2[Int, AB] before looking inside at A(_), and then the A(_) part is only checked to conform with it: there's nothing in

   If the case class is polymorphic, then its type parameters are instantiated so that the instantiation of c conforms to the expected type of the pattern. The instantiated formal parameter types of c's primary constructor are then taken as the expected types of the component patterns p1,…,pn. The pattern matches all objects created from constructor invocations c(v1,…,vn) where each element pattern pi matches the corresponding value vi.

   which would do anything with actual types of p1,…,pn.

Tomkin

Answer 3

Your tuple pattern case (_, _) is just a constructor pattern case Tuple2(_, _).

A constructor pattern with type parameters is inferred like case _: Tuple2[x, y].

Your variable will have the type that is inferred, and you're asking why are x and y inferred the way they are.

In the section on inference in typed patterns, it promises to use the weakest constraints that imply conformance to the expected type.

In this case, the weakest constraints are <: Int and <: AB.

On the other hand, in order to clarify the type of bound variables for pattern matches such as

(Vector.empty: Seq[Nothing]) match { case x @ Nil => x }

which is not a type test but a test for equality, and throws on 2.12 but not 2.13, the spec now says:

The type of the variable x is the static type T implied by the pattern p. A pattern p implies a type T if the pattern matches only values of the type T.

This language might suggest that your intuition is correct, since obviously (_, A(_)) matches only values of type (_, A). This seems to be confirmed by the definition:

The pattern matches all objects created from constructor invocations c(v1,…,vn) where each element pattern pi matches the corresponding value vi.

However, to say the pattern implies a type does not mean the type of the bound variable is the narrowest type implied by the pattern. What could that mean for the Nil example?

Unfortunately, the first form is not yet legal syntax:

case x @ Tuple2[Int @unchecked, A @unchecked](_, A(_)) => x 
case x @ Tuple2(_, A(_)) => x.asInstanceOf[(Int, A)]

Struggle