blog

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.

Some examples of pure functional programs that actually do something.

I’ve been struggling with functional programming lately. The part about using pure functions is very easy for me to get, what was/Is difficult is to understand how does a pure program contact with the outside world and manages to keep state.
I then studied a bit about the IO monad, and I managed to understand how to contact with the outside world. The final piece of the puzzle that I’m still missing is out to piece all this together and how to keep the state in a functional way. I’ve coded some very simple examples to teach myself how these things are done. The examples are scala code and use the scalaz library.

In this first example I just read one line at a time from the prompt and then write it back. The app will do this forever until it is killed. The part that causes it looping forever is done by the recursive function forever, which just repeats the same action over and over:

 def forever(theIO:IO[Unit]):IO[Unit] = theIO >>=| forever(theIO)

I find it quite magical way the way this compact syntax encapsulates the action of just doing something over and over again.

import scalaz._
import Scalaz._
import effects._

/*

This program just echo the input

 */

object Test1 {

  def forever(theIO:IO[Unit]):IO[Unit] = theIO >>=| forever(theIO)

  def functionalMain = {
   forever(for(
      line

On the second example I read one line from the prompt and then add it to a list. I was looking for ways to do this without storing this list anywhere. The method that causes the looping in this case is slightly more complicated, because it has to keep propagating an argument forever, by just passing it to the next action. This way we manage to keep state, a list with all the previous strings, without actually storing this list anywhere. Again, I find this quite magical.

import scalaz._
import Scalaz._
import effects._

object Test2 {

  def getStringAndAddToList(list:List[String]):IO[List[String]] =
    for(
      line (A=>IO[A])):A=>IO[A] = makeIO(_) >>= forever(makeIO)

  def functionalMain = {
    val action = forever(getStringAndAddToList _)
    action(Nil)
  }

  def main(args: Array[String]) {
    functionalMain.unsafePerformIO
  }

}

Tags | pure functional programming, scala, scalaz

lift-json serialization pretty printing

The built-in serialization of lift-json prints a string with no newlines. I prefer to have a nicely printed string so that I can edit the file if I want. For this end I created a new function

writePretty

:

object JsonPimps {

  def writePretty[A <: AnyRef](a: A)(implicit formats: Formats): String =
    (writePretty(a, new StringWriter)(formats)).toString

  def writePretty[A <: AnyRef, W <: Writer](a: A, out: W)(implicit formats: Formats): W =
    Printer.pretty(render(Extraction.decompose(a)(formats)), out)
}

scala – iterate through elements of collection with their indexes

I finally discovered a nice syntax for iterating through a collection with the indices of each element provided:

List(9,9,9,9,9,9).zipWithIndex

res0: List[(Int, Int)] = List((9,0), (9,1), (9,2), (9,3), (9,4), (9,5))

Intellij – git, visual interactive rebasing, local history and SuperCollider

Wow, I’ve just discovered that the git integration in Intellij IDEA is quite advanced. It even does visual interactive rebasing, something which I couldn’t find in any of the shiny looking (and non-free) osx git visual apps.

It also automatically saves your files on every change and kees a private list of changes for the last couple of minutes/hours, which is basically a capable undo system for programmers.

Finally, today I’ve discovered that Intellij is actually a capable editor for SuperCollider classes. I use it to edit classes, but still rely on the SuperCollider app to run the actual code. I’ve made a basic xml file for supercollider syntax support.

I get for free the nice font rendering of plain text, all the git + local history functionality, tabbed editing, and folder layout with all my files. Also, it automatically strips whitespace, and I can position the cursor anywhere in the file and start typing

ScalaCollider – saving presets with json

Sometimes it is useful to save presets when working with ScalaCollider. In Supercollider this is usually done with

writeArchive

and

readArchive

, which can be called on any object that does not contain open functions. After review several possibilities to do the same in scala, I found that the easiest is to use lift-json for JSON parsing and generation. JSON is a human readable format, which is quite convenient.

The easiest way to save a preset would be using case classes to hold the data, since lift-json can automatically serialize and deserialize them:

import java.io.{FileWriter}
import net.liftweb.json._
import net.liftweb.json.Serialization.{write,read}
import scala.io.Source._

object TestJsonSerialization {

  def main(args: Array[String]) {
    implicit val formats = DefaultFormats

    case class Person(name: String, address: Option[String], num:List[Int])
    case class Container(persons:List[Person])
    val people = Container(List(Person("joe", None, List(1,2,3,4)),
        Person("jack", Some("NY grand central"), List(5,6,7,8))))

    //write values to disk
    val fw = new FileWriter("test.txt")
    fw.write(write(people))
    fw.close()

    //get values back
    val jsonString = fromFile("test.txt").mkString
    println(pretty(render(parse(jsonString))))
    println(read[Container](jsonString))
  }

}

To compile the example with sbt use this project file:

import sbt._

class JSONProj(info: ProjectInfo) extends DefaultProject(info)
{
  val json = "net.liftweb" %% "lift-json" % "2.3"
}

Tags | JSON, Presets, scala, ScalaCollider

Scala pattern matching and variables

Today I was debugging some scala code for more than one hour. Turns out that if you use a variable in the pattern you are matching you need to put it in back ticks:

val thing = 3
4 match {
    case thing => println("bingo")
}

This code will match because thing will just became a new variable that is a container for whatever values are being matched.

val thing = 3
4 match {
    case `thing` => println("bingo")
    case _ => println("no match")
}

This code on the other hand will not match, because the variable thing is used, whose content is 3.

Tags | pattern matching, scala

scala compiled to LLVM and Scala.react

Today found a paper submitted at scala days 2011 on “Compiling Scala to LLVM” . That would probably give native speed to scala programs.  I will keep following the development of this.

Also interesting is the paper on “Scala.react: Embedded Reactive Programming in Scala” , also from scala days 2011.