2011 November

Functional fibonacci numbers

There are many ways to calculate the fibonacci numbers sequence in scala, but I really like this one:

def fibs(n:Int)= {
    lazy val fibSeq:Stream[Int] = 0 #:: 1 #:: (fibSeq zip fibSeq.tail).map{ case (a,b) => a+b }
    fibSeq.take(n).toList
}

#:: is the lazy cons method, and fibs zip fibs.tail creates a stream of pairs with the latest two numbers in the sequence.

In haskell it can be even more compact:

fib :: Int -> Integer
fib n = fibs !! n
  where
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

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 ) ) )
  }

}

scala 2.9.1 + sbt 0.11 + Intellij IDEA (10/11) + scala continuations plugin

It took me some time to figure out how to compile a project in Intellij IDEA with the scala continuations plugin turned on. I was getting this error when I ran the project:

bad option: -P:continuations:enable

Here is what you need to do to make it work:

1. In your build.sbt file add:

   autoCompilerPlugins := true
   
   addCompilerPlugin("org.scala-lang.plugins" % "continuations" % "2.9.1")
   
   scalacOptions += "-P:continuations:enable"

2. In sbt run

   reload

   and then

   update

3. Generate the Intellij IDEA project using the sbt command

   gen-idea

4. Open the Intellij IDEA project and go to “Project Structure” -> “Modules” ->”Scala” and add the continuations plugin jar file in the “Compiler Plugins” pane. The jar should be in ~/.ivy2/cache/org.scala-lang.plugins/continuations/jars/continuations-2.9.1.jar .
5. Tick the “Enable Continuations” option in the “Compiler Options” pane.