Compositing functions for Scala filter predicates
When you get past the beginner level of Scala programming, you might feel like filter() is a very basic function that you always know how to use. And then you’re sure to run into situations where it’s just not working and you can’t figure out why.
That happens to me. I try to do something with filter() that looks like it should work, but it doesn’t. After some dead ends and digressions, I figure out what the problem is, and forget about it.
After the third or fourth time going through this, I thought maybe I should write down what the problem is and how I solved it.
The classic example for filter() is to filter out odd numbers from a list of integers. Filtering out even numbers is also very easy.
scala> (1 to 50).filter(_ % 2 == 1)
res0: IndexedSeq[Int] = Vector(1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49)In general, it’s better to get odd or even numbers by means other than filtering. If we wanted to filter by primality, that would make for a more worthwhile use filter().
I don’t think Scala has any built-in primality functions, but it’s easy enough to make one.
@scala.annotation.tailrec
def isPrime(number: Int): Boolean = number match {
case n if n < 0 => isPrime(-n)
case 0 => false
case 1 => false
case n => !((2 until n - 1) exists (n % _ == 0))
}This may not be the most elegant or the most efficient, but it should work just fine for integers close to 0. We can use it to filter out positive integers less than 100 that are not prime.
scala> (1 to 100).filter(isPrime(_))
res1: IndexedSeq[Int] = Vector(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)If we copy and paste the result into Sloane’s OEIS, entry A40, the prime numbers, should come up as the very first search result. We don’t even have to use the wildcard _:
scala> (1 to 100).filter(isPrime)
res2: IndexedSeq[Int] = Vector(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)So far, so good.
Now let’s say we want to know which integers stay or become primes when we reverse their digits (for example, 14 is composite but 41 is prime). It’s very easy in Scala to write a digit reversal function:
def reverseDigits(n: Int): Int =
Integer.parseInt(n.toString.reverse)We don’t even have to worry about the fact that java.lang.String doesn’t actually have reverse(), it’s taken care of for us through an implicit conversion from String to scala.collection.StringOps.
It should be very easy to filter integers that have prime digit reversals, right? Yeah, but only if you have exactly the right syntax.
scala> (1 to 100).filter(isPrime(reverseDigits))
^
error: missing argument list for method reverseDigits
Unapplied methods are only converted to functions when a function type is expected.
You can make this conversion explicit by writing `reverseDigits _` or `reverseDigits(_)` instead of `reverseDigits`.Exact same error message on Scastie. So yeah, let’s go ahead and do that “explicit conversion” thing. No good…
scala> (1 to 100).filter(isPrime(reverseDigits _))
^
error: type mismatch;
found : Int => Int
required: Intscala> (1 to 100).filter(isPrime(reverseDigits(_)))
^
error: type mismatch;
found : Int => Int
required: Int
Once again, we get the same error messages on Scastie as on the local Scala REPL. Maybe we need to use a temporary variable instead of the wildcard? Still doesn’t work…
scala> (1 to 100).filter(n: Int => isPrime(reverseDigits(n)))
^
error: ')' expected but '(' found.
^
error: ';' expected but ')' found.At about this point, I’m getting very frustrated, I start thinking that maybe IntelliJ can help me figure out what it is that I’m doing wrong. So let’s fire up IntelliJ IDEA (presumably you already have the Scala plugin).
Okay, so IntelliJ’s telling me that it “cannot resolve overloaded method filter.” Then I go down a rabbit hole: the Scala documentation for Range lists filter() twice, first as one of the “value members” and second as a “shadowed implicit value member.”
If I’m understanding the documentation correctly, the filter() from TraversableOnce[A] is being shadowed by the filter() from Range. So maybe I need to help the Scala compiler figure out which one is which.
((1 to 100): Range).filter(isPrime(reverseDigits(_))IntelliJ still gives me the error message that it can’t resolve filter(). In hindsight it seems obvious to me now this was a bad idea, but at least I tried it. So how about TraversableOnce[Int]?
((1 to 100): TraversableOnce[Int]).filter(isPrime(reverseDigits(_))Turns out TraversableOnce[A] is now deprecated. But if it works, it works, right? Except it doesn’t. And IntelliJ is showing me “: Int => Int” in gray and underlining it in red near the end of the line.
How about defining a separate named function to wrap the composited function into a single function and pass that to filter()?
scala> def digitsReverseToPrime(n: Int): Boolean =
isPrime(reverseDigits(n))
digitsReverseToPrime: (n: Int)Booleanscala> (1 to 100).filter(digitsReverseToPrime)
res6: IndexedSeq[Int] = Vector(2, 3, 5, 7, 11, 13, 14, 16, 17, 20, 30, 31, 32, 34, 35, 37, 38, 50, 70, 71, 73, 74, 76, 79, 91, 92, 95, 97, 98)
It works, but why should we have to create a new named function we might never use again? There’s got to be a better way. Surely this sort of thing would work in Java if Java had higher order functions…
Maybe now’s the time to look it up in Google. As expected, a lot of results are for Stack Overflow. And as usual, in many of the Stack Overflow answers, it turns out that the problem is caused by something that does not apply to my situation.
So maybe I should ask my own question on Stack Overflow. I start to type it up. They like it if you show that you tried everything you can think of.
I already tried using a temporary local variable without indicating its type, right? It should fail now just like it failed before.
scala> (1 to 100).filter(n => isPrime(reverseDigits(n)))
res7: IndexedSeq[Int] = Vector(2, 3, 5, 7, 11, 13, 14, 16, 17, 20, 30, 31, 32, 34, 35, 37, 38, 50, 70, 71, 73, 74, 76, 79, 91, 92, 95, 97, 98)Well, what do you know? It works! It also works in Scastie. I guess I actually hadn’t tried it before.
I don’t know why the wildcard doesn’t work with the composited function. Maybe someone will explain in the comments.
For now, though, I just want to be sure to write down the solution so that the next time I run into this sort of thing, I can just refer back to this.
I don’t want anyone to walk away with the impression that this kind of thing is unique to Scala. All programming languages have traps for the unwary. Though I think Scala has fewer such traps than languages like C or JavaScript.