Why does Stream.foldLeft use two elements before getting started?
foldLeft only needs one element from the collection before starting. So why is he trying to solve two of them? Can't it be a little lazier?
def stream(i: Int): Stream[Int] =
if (i < 100) {
println("taking")
i #:: stream(i + 1)
} else Stream.empty
scala> stream(97).foldLeft(0) { case (acc, i) =>
println("using")
acc + i
}
taking
taking
using
taking
using
using
res0: Int = 294
I ask this because I have an embedded thread around a mutable priority queue where fold iteration can insert new members into the thread. It starts with one value and enters more values during the first iteration. But these other values are never seen because the stream was already resolved to empty
at position 2 before the first iteration.
source to share
Can only explain why this is happening. Here is the source of the stream #::
( Cons
):
final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A] {
override def isEmpty = false
override def head = hd
@volatile private[this] var tlVal: Stream[A] = _
@volatile private[this] var tlGen = tl _
def tailDefined: Boolean = tlGen eq null
override def tail: Stream[A] = {
if (!tailDefined)
synchronized {
if (!tailDefined) {
tlVal = tlGen()
tlGen = null
}
}
tlVal
}
}
So you can see that it head
always evaluates (is not lazy). Here foldLeft
:
override final def foldLeft[B](z: B)(op: (B, A) => B): B = {
if (this.isEmpty) z
else tail.foldLeft(op(z, head))(op)
}
You can see what is being called here tail
, which means that the "head of tail" (second item) is calculated automatically (as it requires your function stream
to be called again to generate the tail). So the best question is not "why the second" - the question is why stream
always evaluates its first element . I don't know the answer, but I believe the implementation of the scala library can only be improved by creating a head lazy
inside Cons
, so you can go through someLazyCalculation #:: stream(i + 1)
.
Note that your function stream
will be called twice anyway , but the second approach gives you the option to avoid the automatic calculation of the second head by providing some lazy value as the head. Smthng like this might work then (now it doesn't):
def stream(i: Int): Stream[Int] =
if (i < 100) {
lazy val ii = {
println("taking")
i
}
ii #:: stream(i + 1)
} else Stream.empty
PS It's probably not a good idea to build (eventually) an immutable collection around a mutable one.
source to share