Lazy val to implement lazy lists in Scala

Question

I'm trying to learn how to use the built-in laziness in Scala by implementing my own version of lazy lists:

object LazyList {

  def empty[A] : LazyList[A] = new LazyList[A] {
    lazy val uncons = None
  }

  def cons[A](h : => A, t : => LazyList[A]) : LazyList[A] = new LazyList[A] {
    lazy val uncons = Some( (h,t) )
  }

  def from(s : Int) : LazyList[Int] = new LazyList[Int] {
    lazy val uncons = Some( (s,from(s + 1)) )
  }
}

trait LazyList[A] {

  import LazyList._

  def uncons : Option[(A,LazyList[A])]

  def fmap[B](f : A => B) : LazyList[B] = uncons match {
    case None          => empty
    case Some( (h,t) ) => cons(f(h),t.fmap(f))
  }

  def take(i : Int) : LazyList[A] = uncons match {
    case None          => empty
    case Some( (h,t) ) => if (i <= 0) empty else cons(h,t.take(i - 1))
  }

  override def toString : String = uncons match {
    case None          => "[]"
    case Some( (h,t) ) => "[" ++ h.toString ++ ",..]"
  }
}

This seems to work and I can, for instance, map { _ + 2} to the infinite list:

> LazyList from 1 fmap { _ + 2 }
res1: LazyList[Int] = [2,..]

I decided to implement some functions that I usually use like drop, take, etc and I've been able to implement them except for inits. My implementation of inits is:

  def inits : LazyList[LazyList[A]] = uncons match {
    case None          => empty
    case Some( (h,t) ) => cons(empty,t.inits.fmap(cons(h,_)))
  }

The problem is that it doesn't work on infinite lists for some reason. I can't, for example, write:

  > LazyList from 1 inits

because it runs forever. The problem seems to be fmap after t.inits that, for some reason, breaks the laziness (if I remove fmap it is wrong but lazy). Why fmap enforce strictness and, given my type LazyList, how can inits be implemented such that it works on infinite lists?

Answer 1

Both fmap and inits peel one actual (non-lazy) element when invoked; they both uncons. Since they call each other, the chain never terminates on an infinite LazyList.

Specifically, note that uncons returns not a => LazyList but the actual LazyList, so when you call

Some( (h,t) )

that evaluates t. If the evaluation of t calls an uncons, it too will evaluate and you're off to the stack overflow races. It's just tricky to notice here because it's dual recursion.

You need to make one of them peel zero copies. One way you can do that is by making the second argument of the uncons tuple lazy (explicitly, by making it a Function0 instead):

object LazyList {
  def empty[A]: LazyList[A] = new LazyList[A] {
    lazy val uncons = None
  }

  def cons[A](h: => A, t: => LazyList[A]) : LazyList[A] = new LazyList[A] {
    lazy val uncons = Some( (h,() => t) )
  }

  def from(s: Int): LazyList[Int] = new LazyList[Int] {
    lazy val uncons = Some( (s,() => from(s + 1)) )
  }
}

trait LazyList[A] {
  import LazyList._

  def uncons: Option[(A,() => LazyList[A])]

  def fmap[B](f: A => B): LazyList[B] = uncons match {
    case None          => empty
    case Some( (h,t) ) => cons(f(h),t().fmap(f))
  }

  def take(i: Int): LazyList[A] = uncons match {
    case None          => empty
    case Some( (h,t) ) => if (i <= 0) empty else cons(h,t().take(i - 1))
  }

  override def toString: String = uncons match {
    case None          => "[]"
    case Some( (h,t) ) => "[" ++ h.toString ++ ",..]"
  }
}

Then your implementation works:

  def inits: LazyList[LazyList[A]] = uncons match {
    case None          => empty
    case Some( (h,t) ) => cons(empty,t().inits.fmap(cons(h,_)))
  }

It might be nicer to have an internal uncons that did this and an outward-facing uncons that applies the tail for you.