Using Streams for iteration in Scala

Question

SICP says that iterative processes (e.g. Newton method of square root calculation, "pi" calculation, etc.) can be formulated in terms of Streams.

Does anybody use streams in Scala to model iterations?

Answer 1

Here is one way to produce the stream of approximations of pi:

val naturals = Stream.from(0) // 0, 1, 2, ...
val odds = naturals.map(_ * 2 + 1) // 1, 3, 5, ...
val oddInverses = odds.map(1.0d / _) // 1/1, 1/3, 1/5, ...
val alternations = Stream.iterate(1)(-_) // 1, -1, 1, ...
val products = (oddInverses zip alternations)
      .map(ia => ia._1 * ia._2) // 1/1, -1/3, 1/5, ...

// Computes a stream representing the cumulative sum of another one
def sumUp(s : Stream[Double], acc : Double = 0.0d) : Stream[Double] =
  Stream.cons(s.head + acc, sumUp(s.tail, s.head + acc))

val pi = sumUp(products).map(_ * 4.0) // Approximations of pi.

Now, say you want the 200th iteration:

scala> pi(200)
resN: Double = 3.1465677471829556

...or the 300000th:

scala> pi(300000)
resN : Double = 3.14159598691202

Answer 2

Streams are extremely useful when you are doing a sequence of recursive calculations and a single result depends on previous results, such as calculating pi. Here's a simpler example, consider the classic recursive algorithm for calculating fibbonacci numbers (1, 2, 3, 5, 8, 13, ...):

def fib(n: Int) : Int = n match {
  case 0 => 1
  case 1 => 2
  case _ => fib(n - 1) + fib(n - 2)
}

One of the main points of this code is that while very simple, is extremely inefficient. fib(100) almost crashed my computer! Each recursion branches into two calls and you are essentially calculating the same values many times.

Streams allow you to do dynamic programming in a recursive fashion, where once a value is calculated, it is reused every time it is needed again. To implement the above using streams:

val naturals: Stream[Int] = Stream.cons(0, naturals.map{_ + 1})
val fibs : Stream[Int] = naturals.map{
  case 0 => 1
  case 1 => 2
  case n => fibs(n - 1) + fibs( n - 2)
}
fibs(1) //2
fibs(2) //3
fibs(3) //5
fibs(100) //1445263496

Whereas the recursive solution runs in O(2^n) time, the Streams solution runs in O(n^2) time. Since you only need the last 2 generated members, you can easily optimize this using Stream.drop so that the stream size doesn't overflow memory.