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?

Rex Kerr · Accepted Answer · 2014-04-12 23:01:48Z

9

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.

edited Apr 12, 2014 at 23:01

answered Apr 12, 2014 at 15:38

Rex Kerr

168k27 gold badges325 silver badges411 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

mariop Over a year ago

Still strange to me: cons takes t: => LazyList[A] so it is lazy and uncons is a lazy val, so why cons evaluates the tail? If I write cons(f(h),t.fmap(f)), for example, both f(h) and f.fmap(f) should be lazy and not evaluated until needed. Why they are needed?

Rex Kerr Over a year ago

@mariop - Some( (h,t) ) is not lazy. You evaluate the t there. I've edited my answer above to try to highlight this a little more.

Collectives™ on Stack Overflow

Lazy val to implement lazy lists in Scala

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related