MyList - step 7

Introduce laziness: build an infinite list and only compute what you need. We’ll adapt our eager MyList into a lazy version (LzList) that can represent infinite sequences safely. Then we’ll implement take and a generator for infinite lists.

Why laziness? With an eager list, trying to build an infinite structure would never finish. With a lazy list, elements are computed on demand and cached (call-by-need).

Exercise 1: from MyList to LzList

We’ll keep the same API where possible, but change evaluation strategy.

• Rename MyList to LzList (your IDE’s rename refactoring helps).
• Replace Cons with a class that takes head and tail by-name (delayed) and stores them as lazy vals (computed at most once).
• Empty remains a case class (or case object) with the same shape.

Lazy Cons

class Cons[A](hd: => A, tl: => LzList[A]) extends LzList[A]:
  def isEmpty: Boolean = false
  override lazy val head: A = hd
  override lazy val tail: LzList[A] = tl

Notes:

• hd and tl are call-by-name parameters (=>). We wrap them into lazy vals so they are computed at most once (call-by-need).
• We use class rather than case class because case class parameters are evaluated eagerly.
• You’ll instantiate with new Cons(...).

After this change, re-run your small examples to confirm existing map/flatMap/filter semantics still hold, just lazily.

Exercise 2: take and an infinite generator

To see laziness in action, we’ll build an infinite list and take only the first n elements.

• Add take to LzList:

def take(n: Int): LzList[A]

• Add a generator on the companion object to build an infinite integer list by repeatedly applying a step function:

object LzList:
  def generate(start: Int)(next: Int => Int): LzList[Int] = ???

Solution: take

Empty

override def take(n: Int): LzList[A] = this

Cons

override def take(n: Int): LzList[A] =
  def loop(rem: LzList[A], count: Int): LzList[A] =
    if count <= 0 || rem.isEmpty then Empty()
    else new Cons(rem.head, loop(rem.tail, count - 1))
  loop(this, n)

• We stop when count reaches 0 or the list is empty.
• We preserve laziness by constructing Cons with delayed tail.

Solution: generate

object LzList:
  def generate(start: Int)(next: Int => Int): LzList[Int] =
    new Cons[Int](start, generate(next(start))(next))

This creates an infinite list: start, next(start), next(next(start)), and so on. Because Cons is lazy, values are produced only when needed.

Try it out

@main
def main(): Unit =
  val genList: LzList[Int] = LzList.generate(1)(_ + 1)  // 1,2,3,4,...
  val genMap: LzList[Int]  = genList.map(_ * 100)       // 100,200,300,... (lazily)

  println(genMap.take(10))     // first 10 multiples of 100
  println(genMap.take(100))    // first 100
  println(genMap.take(100000)) // still fine, computed on demand

Key ideas

• call-by-name (=>) delays evaluation; lazy val caches the result the first time it’s needed.
• Laziness allows infinite data structures when you only observe a finite prefix (via take).