Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

StreamWithFilter's map and flatMap evaluate one more element than necessary #9134

Closed
scabug opened this issue Feb 4, 2015 · 6 comments
Closed

StreamWithFilter's map and flatMap evaluate one more element than necessary #9134

scabug opened this issue Feb 4, 2015 · 6 comments
Milestone
2.12.0-M1

Comments

@scabug
Copy link

scabug commented Feb 4, 2015

Processing a Stream using its withFilter method evaluates one more element than necessary. When processing a Stream using the filter method, only the necessary elements are evaluated.

Having a simple Stream of natural numbers:

def naturals: Stream[Int] = {
   def loop(i: Int): Stream[Int] = {
      println(s"evaluate $i")
      i #:: loop(i + 1)
   }


   loop(1)
}

Calling map on a Stream filtered using filter vs. withFilter produces the same result, however, withFilter evaluates one more element:

scala> naturals filter(_ % 2 == 0) map(x => x) 
evaluate 1
evaluate 2
res1: scala.collection.immutable.Stream[Int] = Stream(2, ?)

scala> naturals withFilter(_ % 2 == 0) map(x => x)
evaluate 1
evaluate 2
evaluate 3 // this one is eagerly evaluated even though we do not need it
res2: scala.collection.immutable.Stream[Int] = Steam(2, ?)

The behaviour is caused by a call to tail in StreamWithFilter.map and the same problem is in flatMap.

This is a bug, because the semantics of using filter and withFilter should be the same; withFilter should be only an optimization. Moreover, the right behaviour is that of the filter because the Stream operations should be as lazy as possible and in this case there is no reason to evaluate the next element.

As a possible use case where the current behaviour of withFilter manifests as a bug consider the following: having a possibly endless stream of attempts to transactionally perform some computation, try to commit it and if the commit is not successful, perform the transaction anew with new current snapshot of data.

val transAttempts = for {
   trans <- currentTransactionSnapshotStream
   trans.x.increment
   trans.y.decrement
   result = trans.x
   trans.commit
   if (trans.successfullyCommitted)
} yield result

val transactionResult = transAttempts.head

The above code will use withFilter and possibly perform and commit two times. The expected behaviour is that the transaction would be performed and attempted to commit only until it successfully commits the first time.
@scabug
Copy link
Author

scabug commented Feb 4, 2015

Imported From: https://issues.scala-lang.org/browse/SI-9134?orig=1
Reporter: Aurel Paulovič (aurel.paulovic)
Assignee: @ms-tg
Affected Versions: 2.11.5

@scabug
Copy link
Author

scabug commented Feb 4, 2015

@adriaanm said:
See also #8990

@scabug
Copy link
Author

scabug commented Feb 4, 2015

@ms-tg said:
I believe that this will also be fixed by the attendant changes to #8990.
See the PR I have so far here: scala/scala#4284

Essentially, I argue that the WithFilter implementation should absolutely not be re-implementing map/flatMap/foreach, and should implement in terms of a call to #filter followed by the specific call.

Thoughts? I'm happy to add a test of this behavior to the same PR to try to see if we can solve both problems at the same time?

@scabug
Copy link
Author

scabug commented Feb 23, 2015

@ms-tg said:
Update: [~aurel.paulovic] can you confirm that this is fixed on the latest build from the 2.12.x branch?

@adriaanm just merged my fix (scala/scala@198c201) to #8990. As you can see in the linked fix, Stream#withFilter is now essentially little more than a delayed call to Stream#filter, so my expectation is that this issue will have been fixed.

@scabug
Copy link
Author

scabug commented Feb 25, 2015

@ms-tg said:
Hi [~aurel.paulovic], I believe I've confirmed that this issue is fixed in 2.12.x. Please look at the two tests added in the following PR:
scala/scala#4362

Specifically, here's the test that represents the problem you described:
https://github.com/scala/scala/pull/4362/files#diff-31848830800c360c8f0dccca51aedf56R105

@scabug
Copy link
Author

scabug commented Feb 26, 2015

Aurel Paulovič (aurel.paulovic) said:
Hi @ms-tg, the patch looks good to me so I would say it is fixed.

I was not able to run the 2.12.x version of it, but since the test fails for me in 2.11.5, and it does not in 2.12.x, it should be ok.

@scabug scabug closed this as completed Feb 26, 2015
@scabug scabug added this to the 2.12.0-M1 milestone Apr 7, 2017
@scabug scabug mentioned this issue Apr 7, 2017
Closed
@hrhino hrhino mentioned this issue Jul 3, 2018
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
2.12.0-M1
Development

No branches or pull requests
1 participant
@scabug