why does filter have to be defined for pattern matching in a for loop in scala?

Question

To create a new class that can be used in a Scala for comprehension, it seems that all you have to do is define a map function:

scala> class C[T](items: T*) {
     |   def map[U](f: (T) => U) = this.items.map(f)
     | }
defined class C

scala> for (x <- new C(1 -> 2, 3 -> 4)) yield x
res0: Seq[(Int, Int)] = ArrayBuffer((1,2), (3,4))

But that only works for simple for loops where there is no pattern matching on the left hand side of <-. If you try to pattern match there, you get a complaint that the filter method is not defined:

scala> for ((k, v) <- new C(1 -> 2, 3 -> 4)) yield k -> v
<console>:7: error: value filter is not a member of C[(Int, Int)]
       for ((k, v) <- new C(1 -> 2, 3 -> 4)) yield k -> v

Why is filter required to implement the pattern matching here? I would have thought Scala would just translate the above loop into the equivalent map call:

scala> new C(1 -> 2, 3 -> 4).map{case (k, v) => k -> v}
res2: Seq[(Int, Int)] = ArrayBuffer((1,2), (3,4))

But that seems to work fine, so the for loop must be translated into something else. What is it translated into that needs the filter method?

Answer 1

The short answer: according to the Scala specs, you shouldn't need to define a 'filter' method for the example you gave, but there is an open bug that means it is currently required.

The long answer: the desugaring algorithm applied to for comprehensions is described in the Scala language specification. Let's start with section 6.19 "For Comprehensions and For Loops" (I'm looking at version 2.9 of the specification):

In a first step, every generator p <- e, where p is not irrefutable (§8.1) for the type of e is replaced by p <- e.withFilter { case p => true; case _ => false }

The important point for your question is whether the pattern in the comprehension is "irrefutable" for the given expression or not. (The pattern is the bit before the '<-'; the expression is the bit afterwards.) If it is "irrefutable" then the withFilter will not be added, otherwise it will be needed.

Fine, but what does "irrefutable" mean? Skip ahead to section 8.1.14 of the spec ("Irrefutable Patterns"). Roughly speaking, if the compiler can prove that the pattern cannot fail when matching the expression then the pattern is irrefutable and the withFilter call will not be added.

Now your example that works as expected is the first type of irrefutable pattern from section 8.1.14, a variable pattern. So the first example is easy for the compiler to determine that withFilter is not required.

Your second example is potentially the third type of irrefutable pattern, a constructor pattern. Trying to match (k,v) which is Tuple2[Any,Any] against a Tuple2[Int,Int] (see section 8.1.6 and 8.1.7 from the specification)) succeeds since Int is irrefutable for Any. Therefore the second pattern is also irrefutable and doesn't (shouldn't) need a withFilter method.

In Daniel's example, Tuple2[Any,Any] isn't irrefutable against Any, so the withFilter calls gets added.

By the way, the error message talks about a filter method but the spec talks about withFilter - it was changed with Scala 2.8, see this question and answer for the gory details.