Scala Stream call-by-need (leniwy) kontra call-by-name

Question

Rozumiem, że telefoniczne połączenie jest po prostu zapamiętywaną wersją połączenia głosowego. W Kursie FP Johna Odersky'ego na Courserze, w wykładzie 7.3 (Lazy Evaluation), wspomina on, że jeśli strumienie zostały zaimplementowane przy użyciu nazwy wywoławczej, może to potencjalnie doprowadzić do wybuchu złożoności obliczeniowej.

Jaki byłby przykład takiego wybuchu?

Call-by-name:

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

Call-by-potrzebował:

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

Answer 1

Na przykład seria Fibonacciego, realizowany przez dodanie dwóch poprzednich elementów, tworząc następcę. Bez memoization, że musiałby się spowolnienia wzrostu liniowego (i stosu) w długości sekwencji:

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, ?) 

Przykład leniwie (-sic-) skopiowane z this blog