LazyList .scanLeft() called on an empty List

Question

I've been doing some Euler problems in Scala, when I found very elegant solution to #2 problem. However I've got some issues understanding why is it working. As far as I can tell it takes 1 and adds it to fibbonaciNumbers.scanLeft(1)(_ + _) to initialize the same array. How is it possible to call scanLeft() on and LazyList which is empty at the moment?

/**
  * Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2,
  * the first 10 terms will be:
  * 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
  * By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the
  * even-valued terms.
  *
  * Result:
  */
object Problem2 {

  def main(args: Array[String]): Unit = {
    println("The result is " + fibbonaciNumbersSum(4000000))
  }

  // Why is it possible to call .scanLeft on an empty list (because it's empty in the moment we call it, right?)
  lazy val fibbonaciNumbers: LazyList[Int] = 1 #:: fibbonaciNumbers.scanLeft(1)(_ + _)

  private def fibbonaciNumbersSum(limit: Int) = fibbonaciNumbers.takeWhile(_ <= limit).filter(_ % 2 == 0).sum
}

user_1700223 · Answer

The LazyList is not empty. Check the documentation of Stream:

/** Construct a stream consisting of a given first element followed by elements
 *  from a lazily evaluated Stream.
 */
def #::[B >: A](hd: B): Stream[B] = cons(hd, tl)

So at least your Stream/LazyList has a first element (evaluated) and that is 1 from

1 #:: fibbonaciNumbers.scanLeft...

The second element in the list is the 1 from the scanLeft ... and then the scanLeft takes over in order to generate the rest of the elements 2, 3, 5...but they will only be evaluated when needed. But when are they needed ? ... When you call

println("The result is " + fibbonaciNumbersSum(4000000))

and this will trigger the evaluation of

fibbonaciNumbers.takeWhile(_ <= limit).filter(_ % 2 == 0).sum

So each element in the Stream / LazyList will be evaluated as long as they are less than limit and the the filtering and the summation will be done.

LazyList .scanLeft() called on an empty List

1 Answers