Using Streams for iteration in Scala

问题:

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?

回答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

回答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.