Applying a function to just one previous term in a Scala lazy collection
The Fibonacci sequence is the classic example for lazy collections in Scala. As you know, the Fibonacci numbers start with 0 and 1, then each Fibonacci number after that is the sum of the previous two Fibonacci numbers.
The sequence, as readers of The Da Vinci Code by Dan Brown might know, starts out 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. Note that 0 is the zeroth Fibonacci number, and 1 is both the first and second Fibonacci numbers.
Looking at entry A45 in Sloane’s OEIS, we see that the Fibonacci numbers get large quickly. The 47th Fibonacci number is 2971215073. That’s large enough to be misunderstood as −1323752223 in a 32-bit integer.
So we have to use something like Java’s BigInteger or Scala’s BigInt. And obviously we have to apply the plus function to two previous terms. This is an implementation taken straight from the Scala documentation:
val fibs: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 }If you have a Scala REPL on your system, go ahead and try it out.
scala> fibs(100)
res12: BigInt = 354224848179261915075That’s too big even for a 64-bit integer (in this example, you can use res12.bitLength to see by how many bits this would overflow a Long).
The advantage of “laziness” here is that beyond the initial 0 and 1, the computer calculates the Fibonacci sequence only to the index we ask for. If we only ask for, say, the tenth Fibonacci number, the computer will not calculate the eleventh.
And if after asking for the tenth Fibonacci number we ask for the thousandth, the computer will not recalculate the first ten Fibonacci numbers, it will go forward from the eleventh to the thousandth.
The lazy approach is definitely more efficient than plain recursion. Plain recursion is soon taxed by extremely slow performance for even small indices. For example:
def fibonacci(n: Int): BigInt = n match {
case n if n < 0 => (if (n % 2 == 0) -1 else 1) * fibonacci(-n)
case 0 => 0
case 1 => 1
case n => fibonacci(n - 2) + fibonacci(n - 1)
}In the Scastie snippet, I use it for just −10 to 10, and it apparently works at the same speed as the lazy val. But if you ask Scastie for fibonacci(100), you will get timed out.
And on your local Scala REPL, you’ll probably get so tired of waiting you will quit the REPL and restart it.
scala> (-10 to 10).map(fibonacci(_))
res13: IndexedSeq[BigInt] = Vector(-55, 34, -21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)scala> fibonacci(100)
Terminate batch job (Y/N)? yC:\Users\AL>scala
Welcome to Scala 2.13.1 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_251).
Type in expressions for evaluation. Or try :help.scala> 1 + 1
res0: Int = 2
A Fibonacci algorithm with tail recursion works much better than the plain recursion, but it still does not take advantage of previously computed values.
So, regardless of previous calls, a recursive function will require the same number of steps for any given input. Ask for the tenth Fibonacci number and then the eleventh Fibonacci number, and the recursive function will have to calculate the tenth Fibonacci number again, and its predecessors.
The only advantage to defining a function like this is that we can extend the domain of the function to negative numbers. But this is not a one-or-the-other situation. We can definitely have both the performance of the lazy collection and the ability to obtain Fibonacci numbers for negative indices.
For this next example, I assume that you got tired of waiting for the recursion to deliver the hundredth Fibonacci number, so you quit the REPL and started it back up.
So paste in again the definition for fibs from above, and then paste this in:
def fibonacci(n: Int): BigInt = if (n < 0) {
fibs(-n) * (if (n % 2 == 0) -1 else 1)
} else fibs(n)Then, just like before, this should be able to give you the Fibonacci numbers for −10 to 10 in no time flat:
scala> (-10 to 10).map(fibonacci(_))
res1: IndexedSeq[BigInt] = Vector(-55, 34, -21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)And, with barely a hiccup for a delay:
scala> fibonacci(-100)
res2: BigInt = -354224848179261915075No worries about getting timed out in the Scastie snippet either.
You might see the lazy Fibonacci example elsewhere online using Stream instead of LazyList. The former is deprecated in favor of the latter as of Scala 2.13.0. The old API documentation for Stream had pretty much the same Fibonacci example, differing only in the use of Stream instead of LazyList.
But what if you only need one previous item in the lazy collection to compute the next item? Surely it’s got to be easier than applying a function to two previous terms like in the Fibonacci sequence, right?
The solution is indeed easy, and it’s the same for both Stream and LazyList: you use iterate, which is defined in each class’s “companion object.”
This is not something I just knew somehow, I had to do a bit of Internet digging to figure it out. The answer is out there, but I found it through a very circuitous path.
There might not be a page out there that plainly says: “Use iterate when you want evaluate lazily in Scala based only on one previous term.”
So I thought I should post the solution here on Medium, for my own convenience and the convenience of others who can’t figure it out from the Fibonacci example either.
For the example, we’ll use the powers of 7, that is, 7⁰ = 1, 7¹ = 7, 7² = 49, 7³ = 343, 7⁴ = 2401, 7⁵ = 16807, 7⁶ = 117649, 7⁷ = 823543, etc. After 1, each term is the previous term multiplied by 7: 7 × 7 = 49, 49 × 7 = 343, 343 × 7 = 2401, 2401 × 7 = 16807, etc.
It’s a different problem. With the Fibonacci numbers we need the previous two terms because we need to add two numbers that are always distinct (except for 1 and 1 early on).
But for the powers of 7, even though multiplication is a two-operand function just like addition, we only need the previous term because only one of the two multiplicands changes. The other multiplicand is always 7.
Even so, let’s try to adapt the syntax from the lazy Fibonacci implementation to the powers of 7 problem.
scala> val pow7Attempt: LazyList[BigInt] = BigInt(1) #:: BigInt(7) #:: pow7Attempt.zip(pow7Attempt.tail).map { n => n._2 * 7 }
pow7Attempt: LazyList[BigInt] = LazyList(<not computed>)scala> pow7Attempt.takeWhile(_ < Integer.MAX_VALUE).toList
res3: List[BigInt] = List(1, 7, 49, 343, 2401, 16807, 117649, 823543, 5764801, 40353607, 282475249, 1977326743)
Huh. That actually worked. But it’s ugly: zip gives the two previous terms in a pair, but in map we’re only using n._2 (the immediately previous term) and completely ignoring n._1.
How about lazyZip? But I don’t know what a LazyZip2 decorator is, and that would probably be a major rabbit hole that yields nothing useful for the problem at hand.
The syntax we really want here is LazyList.iterate(start)(function). And in this case, we can use the underscore wildcard in our function literal.
scala> val powersOf7: LazyList[BigInt] = LazyList.iterate(1: BigInt)(_ * 7)
powersOf7: LazyList[BigInt] = LazyList(<not computed>)Function currying is the reason for the two sets of parentheses in the declaration of powersOf7. Currying is a topic for another article.
Here, suffice it to say that iterate applies the function (multiply by 7), first to the starting value (1 as a BigInt), then to that product, and then to the product of that product, and so on and so forth. But each time, only one previous parameter is fed to the multiply by 7 function.
scala> (0 to 13).map(powersOf7(_))
res4: IndexedSeq[BigInt] = Vector(1, 7, 49, 343, 2401, 16807, 117649, 823543, 5764801, 40353607, 282475249, 1977326743, 13841287201, 96889010407)Easy enough. Just to be sure, let’s try to practice this with similar problems.
Sometimes psychiatrists ask their Alzheimer’s patients to count backwards from 100 in steps of 7. It’s trivially simple for the computer to do this, but it’s also a good opportunity to review takeWhile. The starting value is 100, and the function is to subtract 7.
scala> val serialSevens: LazyList[Int] = LazyList.iterate(100)(_ - 7)
serialSevens: LazyList[Int] = LazyList(<not computed>)scala> serialSevens.takeWhile(_ > 0).toList
res7: List[Int] = List(100, 93, 86, 79, 72, 65, 58, 51, 44, 37, 30, 23, 16, 9, 2)
I figure the shrink would stop the patient well before getting down to 2, and even without a cue, the patient would probably not proceed to −5. And that’s as far as the computer has gone.
scala> serialSevens
res8: LazyList[Int] = LazyList(100, 93, 86, 79, 72, 65, 58, 51, 44, 37, 30, 23, 16, 9, 2, -5, <not computed>)It went down to −5 only to make sure the number is not positive. The “<not computed>” at the end is LazyList’s way of telling us it doesn’t have any more numbers of this sequence, but can get us more if we want them.
Now for something a little more “complex,” but still only using one previous term of the lazy collection. If you don’t already have a tested and proven ComplexNumber class you can use, here’s a bare-bones version that will suffice for the example:
class ComplexNumber(val re: Double, val im: Double = 0.0) { def +(addend: ComplexNumber): ComplexNumber =
new ComplexNumber(this.re + addend.re, this.im + addend.im) def *(multiplicand: ComplexNumber): ComplexNumber =
new ComplexNumber(this.re * multiplicand.re - this.im *
multiplicand.im,
this.re * multiplicand.im + this.im * multiplicand.re) override def toString: String = this.re.toString + " + " +
this.im.toString + "i"}
Theoretically, this is good enough to crunch the numbers to draw the Mandelbrot set. Though toString leaves something to be desired for complex numbers with negative imaginary part.
The function we need to draw the Mandelbrot set is z² + c, where c is constant through the iterations of the function, and the initial value of z can be either 0 or c (no human will notice the performance gain from starting with c).
Since c is constant, the only necessary new information at each step is the previous value of z.
scala> val zero = new ComplexNumber(0.0)
zero: ComplexNumber = 0.0 + 0.0iscala> val douadyRabbit = new ComplexNumber(-0.12256, 0.74486)
douadyRabbit: ComplexNumber = -0.12256 + 0.74486iscala> val mandelEscape: LazyList[ComplexNumber] = LazyList.iterate(zero)(z => z * z + douadyRabbit)
mandelEscape: LazyList[ComplexNumber] = LazyList(<not computed>)scala> mandelEscape.take(10).toList
res10: List[ComplexNumber] = List(0.0 + 0.0i, -0.12256 + 0.74486i, -0.662355466 + 0.5622799168i, -3.941496537818168E-6 + 1.6473709895103994E-6i, -0.12255999998717844 + 0.7448599999870138i, -0.662355465983797 + 0.5622799168222836i, -3.9415430613254365E-6 + 1.6473596913257893E-6i, -0.12255999998717804 + 0.7448599999870137i, -0.662355465983797 + 0.5622799168222843i, -3.9415430620470815E-6 + 1.6473596904376109E-6i)
I’ve also put this one in a Scastie snippet.
Of course we’re not limited to numeric data types for iterate. The following example is of little practical value, but hopefully it gets the point across.
scala> val reflections: LazyList[String] = LazyList.iterate("Hello")(s => s + s.reverse)
reflections: LazyList[String] = LazyList(<not computed>)scala> reflections.takeWhile(_.length < 100).toList
res12: List[String] = List(Hello, HelloolleH, HelloolleHHelloolleH, HelloolleHHelloolleHHelloolleHHelloolleH, HelloolleHHelloolleHHelloolleHHelloolleHHelloolleHHelloolleHHelloolleHHelloolleH)
If you want, you can come up with more examples. Please feel free to post them in the comments if you do.
One more thing: in an integrated development environment like IntelliJ IDEA, you might get forward reference errors. Just add the keyword “lazy” before the pertinent val declarations, that should clear up the errors.
