Inside the LazyList, why `head` is implement by `def`?

Question
1

When I dig into source code of LazyList

// scala 2.13.2 scala/collection/immutable/LazyList.scala

  /** @inheritdoc
    *
    * This method does not evaluate any elements further than
    * the first element matching the predicate.
    */
  @tailrec
  override def find(p: A => Boolean): Option[A] =
    if (isEmpty) None
    else {
      val elem = head
      if (p(elem)) Some(elem)
      else tail.find(p)
    }

Here defined a variable elem to store the head result.

What’s more

  override def head: A = state.head

  private lazy val state: State[A] = {
    // if it's already mid-evaluation, we're stuck in an infinite
    // self-referential loop (also it's empty)
    if (midEvaluation) {
      throw new RuntimeException("self-referential LazyList or a derivation thereof has no more elements")
    }
    midEvaluation = true
    val res = try lazyState() finally midEvaluation = false
    // if we set it to `true` before evaluating, we may infinite loop
    // if something expects `state` to already be evaluated
    stateEvaluated = true
    lazyState = null // allow GC
    res
  }

My question is:
Why cant we just write override val head: A = state.head?
If so, in find method, we can write

  @tailrec
  override def find(p: A => Boolean): Option[A] =
    if (isEmpty) None
    else {
      if (p(head)) Some(head)
      else tail.find(p)
    }
1 Like
2

If head was a val then LazyList wouldn’t be lazy.

You could argue it could be a lazy val, but then it actually would have worse performance than def in this case.

3

It actually would have worse performance than def in this case.

Could you explain it in detail？I don’t know this part very well.
IMO, lazy val only calculate once, def will calculate after every invoke.

4

IMO, lazy val only calculate once, def will calculate after every invoke.

Yes, that is right. However, a lazy val implies a monitor (a concurrent lock) which ensures only one thread at a time is trying to read the value, it also implies checking a boolean value to see if the value was already computed or not.
Those two things make accessing a lazy val quite slow. So the idea is that you should be sure that the computation you are doing the first time has to be very big so the extra cost of accessing it is wort it.

Now let’s see the code again:

override def head: A = state.head

private lazy val state: State[A] = ...

So, head basically delegates to state, which is already a lazy val; and that is the one that will do the heavy computation and cache the results.
So, making head another lazy val would just add another lock and another check for nothing, it is better to just forward to state.

Now in this other piece of code:

@tailrec
override def find(p: A => Boolean): Option[A] =
  if (isEmpty) None
  else {
    val elem = head
    if (p(elem)) Some(elem)
    else tail.find(p)
  }

elem is created as an optimization, to only go thought the forwarder and acquiring the lock and all that just once.

2 Likes
5

For more detail on this, it’s worth taking a look at SIP-20, which talks extensively about how lazy val works and how it might be improved. It’s quite eye-opening: every lazy val winds up generating quite a lot of code. (And proposals to improve it mostly involve even more code.)

5 Likes