freedev freedev - 4 months ago 27
Scala Question

Scala stream filter behaviour

I'm playing with scala streams.
Here is the stream of all integers starting from a given number.
I have added a

println
to trace every call of from function.

def from(n: Int): Stream[Int] = n #:: from({ println(n); n + 1 })

val nats = from(0) //> nats : Stream[Int] = Stream(0, ?)

nats.take(4).toList //> 0
//| 1
//| 2
//| 3
//| res0: List[Int] = List(0, 1, 2, 3, 4)


As expected, this is the output of my scala worksheet. Then I have created the stream of all prime numbers.

def sieve(s: Stream[Int]): Stream[Int] = {
s.head #:: sieve(s.tail.filter({ println( "---" ); _ % s.head != 0 }))
} //> sieve: (s: Stream[Int])Stream[Int]

val primes = sieve(from(2))//> primes : Stream[Int] = Stream(2, ?)

primes.take(4).toList //> 2
//| ---
//| 3
//| 4
//| ---
//| 5
//| 6
//| ---
//| res1: List[Int] = List(2, 3, 5, 7)


Here comes the question. I have made what in my opinion should be a little change, adding the
x
parameter instead of
_
placeholder. Surprisingly the output is quite different:

def sieve(s: Stream[Int]): Stream[Int] = {
s.head #:: sieve(s.tail.filter(x => { println("---"); (x % s.head) != 0 }))
} //> sieve: (s: Stream[Int])Stream[Int]

val primes = sieve(from(2))//> primes : Stream[Int] = Stream(2, ?)

primes.take(4).toList //> 2
//| ---
//| 3
//| ---
//| 4
//| ---
//| ---
//| 5
//| ---
//| 6
//| ---
//| ---
//| ---
//| res1: List[Int] = List(2, 3, 5, 7)


I don't understand why all these repetitions.
What's wrong in using the explicit parameter?

Answer

The difference is because { println( "---" ); _ % s.head != 0 } is short for { println( "---" ); x => x % s.head != 0 } rather than { x => println( "---" ); x % s.head != 0 }.

In the first case you first call println and then return the function, so --- is printed once per filter call; in the second it's once per filter call per element of the stream being filtered (and because sieve is recursive and filters the stream again, you end up with multiple --- for each element of the output).