Scala Standard Library 2.13.15 - scala.collection.immutable (original) (raw)

This class implements an immutable linked list. We call it "lazy" because it computes its elements only when they are needed.

Elements are memoized; that is, the value of each element is computed at most once.

Elements are computed in-order and are never skipped. In other words, accessing the tail causes the head to be computed first.

How lazy is a LazyList? When you have a value of type LazyList, you don't know yet whether the list is empty or not. If you learn that it is non-empty, then you also know that the head has been computed. But the tail is itself a LazyList, whose emptiness-or-not might remain undetermined.

A LazyList may be infinite. For example, LazyList.from(0) contains all of the natural numbers 0, 1, 2, and so on. For infinite sequences, some methods (such as count, sum, max or min) will not terminate.

Here is an example:

import scala.math.BigInt object Main extends App { val fibs: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map{ n => n._1 + n._2 } fibs.take(5).foreach(println) }

// prints // // 0 // 1 // 1 // 2 // 3

To illustrate, let's add some output to the definition fibs, so we see what's going on.

import scala.math.BigInt object Main extends App { val fibs: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map{ n => println(s"Adding n.1and{n._1} and n.1​and{n._2}") n._1 + n._2 } fibs.take(5).foreach(println) fibs.take(6).foreach(println) }

// prints // // 0 // 1 // Adding 0 and 1 // 1 // Adding 1 and 1 // 2 // Adding 1 and 2 // 3

// And then prints // // 0 // 1 // 1 // 2 // 3 // Adding 2 and 3 // 5

Note that the definition of fibs uses val not def. The memoization of theLazyList requires us to have somewhere to store the information and a val allows us to do that.

Further remarks about the semantics of LazyList:

Here's another example. Let's start with the natural numbers and iterate over them.

// We'll start with a silly iteration def loop(s: String, i: Int, iter: Iterator[Int]): Unit = { // Stop after 200,000 if (i < 200001) { if (i % 50000 == 0) println(s + i) loop(s, iter.next(), iter) } }

// Our first LazyList definition will be a val definition val lazylist1: LazyList[Int] = { def loop(v: Int): LazyList[Int] = v #:: loop(v + 1) loop(0) }

// Because lazylist1 is a val, everything that the iterator produces is held // by virtue of the fact that the head of the LazyList is held in lazylist1 val it1 = lazylist1.iterator loop("Iterator1: ", it1.next(), it1)

// We can redefine this LazyList such that all we have is the Iterator left // and allow the LazyList to be garbage collected as required. Using a def // to provide the LazyList ensures that no val is holding onto the head as // is the case with lazylist1 def lazylist2: LazyList[Int] = { def loop(v: Int): LazyList[Int] = v #:: loop(v + 1) loop(0) } val it2 = lazylist2.iterator loop("Iterator2: ", it2.next(), it2)

// And, of course, we don't actually need a LazyList at all for such a simple // problem. There's no reason to use a LazyList if you don't actually need // one. val it3 = new Iterator[Int] { var i = -1 def hasNext = true def next(): Int = { i += 1; i } } loop("Iterator3: ", it3.next(), it3)

In the fibs example earlier, the fact that tail works at all is of interest.fibs has an initial (0, 1, LazyList(...)), so tail is deterministic. If we defined fibs such that only 0 were concretely known, then the act of determining tail would require the evaluation of tail, so the computation would be unable to progress, as in this code:

// The first time we try to access the tail we're going to need more // information which will require us to recurse, which will require us to // recurse, which... lazy val sov: LazyList[Vector[Int]] = Vector(0) #:: sov.zip(sov.tail).map { n => n._1 ++ n._2 }

The definition of fibs above creates a larger number of objects than necessary depending on how you might want to implement it. The following implementation provides a more "cost effective" implementation due to the fact that it has a more direct route to the numbers themselves:

lazy val fib: LazyList[Int] = { def loop(h: Int, n: Int): LazyList[Int] = h #:: loop(n, h + n) loop(1, 1) }

The head, the tail and whether the list is empty or not can be initially unknown. Once any of those are evaluated, they are all known, though if the tail is built with #:: or #:::, it's content still isn't evaluated. Instead, evaluating the tails content is deferred until the tails empty status, head or tail is evaluated.

Delaying the evaluation of whether a LazyList is empty or not until it's needed allows LazyList to not eagerly evaluate any elements on a call to filter.

Only when it's further evaluated (which may be never!) any of the elements gets forced.

for example:

def tailWithSideEffect: LazyList[Nothing] = { println("getting empty LazyList") LazyList.empty }

val emptyTail = tailWithSideEffect // prints "getting empty LazyList"

val suspended = 1 #:: tailWithSideEffect // doesn't print anything val tail = suspended.tail // although the tail is evaluated, still nothing is yet printed val filtered = tail.filter(_ => false) // still nothing is printed filtered.isEmpty // prints "getting empty LazyList"

You may sometimes encounter an exception like the following:

java.lang.RuntimeException: "LazyList evaluation depends on its own result (self-reference); see docs for more info

This exception occurs when a LazyList is attempting to derive its next element from itself, and is attempting to read the element currently being evaluated. A trivial example of such might be

lazy val a: LazyList[Int] = 1 #:: 2 #:: a.filter(_ > 2)

When attempting to evaluate the third element of a, it will skip the first two elements and read the third, but that element is already being evaluated. This is often caused by a subtle logic error; in this case, using >= in the filter would fix the error.