Using streams in scala for functional style programming

The paper “why functional programming matters” by John Hughes is a very nice example of using streams to calculate an approximation of the square root of a number using the Newton method.

The #:: method is a lazy cons, that only calculates the element to be added to the head of the list when needed. The repeat function creates a stream by repeatedly applying f to the last element of the  stream starting from the value a. The within function keeps looking for better matches in the stream until the successive values are close enough to each other. By chaining these functions you get the result:

/**
 *
 * Newton-Raphson Square Roots
 * as is shown in "why functional programming matters"
 * http://www.cs.utexas.edu/~shmat/courses/cs345/whyfp.pdf
 */

object NewtonRoots {

  //algorithm to approach the square root of n
  def next(n:Double)(x:Double) = (x + n/x)/2

  //create a stream composed of repeatedly applying f
  def repeat(f:Double=>Double, a:Double):Stream[Double] = a #:: repeat(f,f(a))

  //look for a good enough match in the stream
  def within(eps:Double, s:Stream[Double]):Double = s match {
    case a #:: b #:: rest => if( (a-b).abs < eps) b else within(eps, b#::rest)
  }

   //look for a good enough match in the stream.
   // A better way is to see how close a/b is to 1,
   // to avoid the rounding errors
  def relative(eps:Double, s:Stream[Double]):Double = s match {
    case a #:: b #:: rest => if( (a/b -1).abs < eps) b else within(eps, b#::rest)
  }

  //find the square root of 3 starting from the approximation
  // value 1, until approximations are within 0.01
  def main(args: Array[String]) {
    println( within(0.01, repeat( next(3), 1 ) ) )
  }

}