LazyList in Scala

user_1298028 0
Viewed 885

Assume that we have the following LazyList definition:

val fibs: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #::
fibs.zip(fibs.tail).map(pair => pair._1 + pair._2)

My question is how is that executed, because this definition says that we take the tail and we do computation for each pair (from the zip). But if we want to calculate element with index 10 we already have values for ...8, 9. So the question is... is this somehow optimized, or for each next element we go through all the pairs?

scala
1 Answers

Adding on-

  1. LazyList is essentially a LinkedList, this would mean that in order to access 10th element you'd have to go through all first.

  2. The #:: operator/method essentially ends up creating a new class, this is the library code-

    implicit def toDeferrer[A](l: => LazyList[A]): Deferrer[A] = new Deferrer[A](() => l)

final class Deferrer[A] private[LazyList] (private val l: () => LazyList[A]) extends AnyVal {

  /** Construct a LazyList consisting of a given first element followed by elements
    *  from another LazyList.
    */
  def #::[B >: A](elem: => B): LazyList[B] = newLL(sCons(elem, l()))

  /** Construct a LazyList consisting of the concatenation of the given LazyList and
    *  another LazyList.
    */
  def #:::[B >: A](prefix: LazyList[B]): LazyList[B] = prefix lazyAppendedAll l()
}

The order of object creation then would be-

  1. Lazily wrapped in Function0 fibs.zip(fibs.tail).map(pair => pair._1 + pair._2)
  2. Afterwards we have the cons operator #:: available, we attach a new head BigInt(1)
  3. Lastly, we again attach a new head to the LinkedList BigInt(0), now our recursive structure is ready.
  4. Again everything is still constructed lazily, that's why we don't end up dereferencing null

When we call head, we start unwrapping and then the laziness starts taking action.

Furthermore, LazyList internally uses this State structure to model the head and tail

private sealed trait State[+A] extends Serializable {
  def head: A
  def tail: LazyList[A]
}

and this structure is what it memoizes on first access for each of the elements.

private lazy val state: State[A] = { ... }
user_79767440
Related