Scala Stream call-by-need (lazy) vs call-by-name

Question

So I understand that call-by-need is simply a memoized version of call-by-name. In Martin Odersky's FP Course on Coursera, in lecture 7.3 (Lazy Evaluation), he mentions that if Streams were implemented using call-by-name, then it could potentially lead to a blowup in computational complexity.

What would be an example of such a blowup?

Call-by-name:

def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
  def head = hd
  def tail = tl
  ...
}

Call-by-need:

def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
  def head = hd
  lazy val tail = tl
  ...
}

Scram

Answer 1

For example the Fibonacci series, implemented by adding the previous two elements to form the successor. Without memoization, that would have a linear slowdown (and stack growth) in the length of the sequence:

scala> lazy val fib: Stream[Int] = Stream.cons(0,
     | Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)))
fib: Stream[Int] = Stream(0, ?)

Example lazily (-sic-) copied from this blog

Convex

Please check link, – Known

Answer 2

def and lazy val are both lazy. The difference is that def is re-evaluated every time it is called. lazy val is only evaluated the first time it is called and any call to it just looks to the first evaluated value.

Using def would mean re-evaluated tail every time it is called.

def randDef: () => Int = {
  val r = scala.util.Random.nextInt
  () => r
}

val randVal: () => Int = {
  val r = scala.util.Random.nextInt
  () => r
}

lazy val randLazyVal: () => Int = {
  val r = scala.util.Random.nextInt
  () => r
}
// defined function randDef
// randVal: () => Int = ammonite.$sess.cmd18$Helper$$Lambda$2545/0x00000008013a4430@7466fa3
// randLazyVal: () => Int = [lazy]

randDef()
// res8: Int = -693604502
randDef()
// res9: Int = 2056941756
randDef eq randDef
// res15: Boolean = false

randVal()
// res11: Int = 3
randVal()
// res12: Int = 3
randVal eq randVal
// res16: Boolean = true

randLazyVal()
// res13: Int = 99
randLazyVal()
// res14: Int = 99
randLazyVal eq randLazyVal
// res17: Boolean = true

Siple