Tag Archives: scala

Upcoming Coursera course: Principles of Reactive Programming

Just a quick note to say that a new Coursera course begins on 4th Nov 2013 that looks very interesting indeed titled ‘Principles of Reactive Programming‘ taught by Martin Odersky, Erik Meijer and Roland Kuhn. It is intended as a follow on course from its precursor course ‘Functional Programming Principles in Scala‘ also taught by Martin Odersky that concludes right when the new one starts. To hear the instructors give an introduction to the new course watch this video.

Scala Cookbook: Simplifying nested pattern matching

Pattern matching in Scala is a natural and intuitive way of expressing branched logic and can greatly simplify complex branched logic in terms of readability but what if you need to branch within a branch? This can result in unsightly code and duplication of logic. Let’s see this first hand with an example.

Let’s try to code a function removeAt(n, List) which removes the zero indexed nth element from the supplied list and returns the resulting list. Our first attempt, as we transcribe our thoughts step by step into code, may look as follows.

  def removeAt[T](n: Int, xs: List[T]): List[T] = n match {
    case 0 => xs match {
      case Nil => Nil
      case y :: ys => removeAt(n - 1, ys)
    }
    case _ => xs match {
      case Nil => Nil
      case y :: ys => y :: removeAt(n - 1, ys)
    }
  }

Here you can see that, although the logic is correct and reasonably easy to interpret, there is duplication of code and the function could be made even easier to read and a little shorter. On our second attempt we may try to extract the duplicate Nil => Nil cases outside of the match as below.

  def removeAt[T](n: Int, xs: List[T]): List[T] =
    if (xs.isEmpty) Nil else n match {
      case 0 => xs match {
        case y :: ys => removeAt(n - 1, ys)
      }
      case _ => xs match {
        case y :: ys => y :: removeAt(n - 1, ys)
      }
    }

This also works and has in fact achieved our goals – the function is shorter and does not duplicate code. However, at this point, it is blending if/else logic with pattern matching and most importantly producing warnings in Scala IDE in Eclipse. The warnings state that in our secondary (internal) pattern match we do not cater for the Nil case and that’s correct.

Description	Resource	Path	Location	Type
match may not be exhaustive. It would fail on the following input: Nil	ListUtils.scala	/scala-test/src/week5	line 13	Scala Problem
match may not be exhaustive. It would fail on the following input: Nil	ListUtils.scala	/scala-test/src/week5	line 16	Scala Problem

Even though Scala IDE may not see that in the bigger picture the logic is actually correct it is correct in saying what it is saying specifically and I also consider it bad practice to leave warnings in code so let’s go through one more simplification attempt. How else can we restructure this function to achieve the same goals?

  def removeAt[T](n: Int, xs: List[T]): List[T] =
    xs match {
      case Nil => Nil
      case y :: ys => n match {
        case 0 => removeAt(n - 1, ys)
        case _ => y :: removeAt(n - 1, ys)
      }
    }

The answer is to invert the order of the high level pattern match subjects by making the subject that’s being pattern matched redundantly rise to become the primary pattern match with the other subject then becoming secondary. And there we have the end result of the simplification.

Addendum

A couple of after thoughts for completion follow here. Firstly – the above progression in implementation strategies was chosen to allow illustration of how to incrementally simplify a function and does not suggest that one cannot in fact end up with the final solution the first time. Secondly – the implementation algorithm above which is needlessly verbose has also been chosen to be illustrative of nested pattern matching and isn’t the simplest and most concise possible solution. For that see below.

  def removeAt[T](n: Int, xs: List[T]): List[T] =
    (xs take n) ::: (xs drop n+1)

Scala Cookbook: Tail recursive factorial

The direct port of a human readable description of the factorial algorithm may look as follows.

  def factorial(x: BigInt): BigInt = {
    if (x == 0) 1 else x * factorial(x - 1)
  }

However – this isn’t tail recursive and will fail for large inputs.

Exception in thread "main" java.lang.StackOverflowError
	at java.math.BigInteger.getInt(BigInteger.java:3014)

The classic nested accumulator helper function idiom can be used to make this tail recursive.

  def factorial(x: BigInt): BigInt = {
    @tailrec
    def f(x: BigInt, acc: BigInt): BigInt = {
      if (x == 0) acc else f(x - 1, x * acc)
    }
    f(x, 1)
  }

So what’s going on here? Well it’s quite simple really.

The first function uses a number of stack frames proportional to the size of the input due to the fact that it is using right expansion. In other words when it calls itself it multiplies the result by x tainting the stack so that it can’t be thrown away or reused. The stack is only flattened when fully expanded and then collapsed.

The second function is tail recursive – in other words – it calls itself as the final call. This is essentially compiled to a loop by the Scala compiler using only one stack frame regardless of the size of the input. It is therefore not possible to get a StackOverflowError with a tail recursive function.

Note the @tailrec annotation which when applied if it compiles then your function is certified tail recursive by the Scala compiler. It is a quick and easy way to check whether your function is tail recursive at compile time as well as serving as a useful hint for other developers maintaining your code.

A pattern matched equivalent of the tail recursive function for fun is below.

  def factorial4(x: BigInt): BigInt = {
    @tailrec
    def f(x: BigInt, acc: BigInt): BigInt = x match {
      case y: BigInt if y == 0 => acc
      case _ => f(x - 1, x * acc)
    }
    f(x, 1)
  }

Scala Cookbook: Pattern matching on BigInt

Let’s take the factorial algorithm as an example.

  def factorial(x: BigInt): BigInt = {
    if (x == 0) 1 else x * factorial(x - 1)
  }

One might expect to convert this into a pattern matched equivalent as follows.

  def factorial(x: BigInt): BigInt = x match {
    case 0 => 1
    case _ => x * factorial(x - 1)
  }

In fact this will give you the error below.

type mismatch;  found   : Int(0)  required: BigInt	Factorial.scala

The reason is that BigInt is not a case class and does not have an unapply() method in its companion object.

However a small modification allows the pattern matching implementation to succeed.

  def factorial(x: BigInt): BigInt = x match {
    case y: BigInt if y == 0 => 1
    case _ => x * factorial(x - 1)
  }

Arguably the if/else equivalent is simpler but if you always use pattern matching you’ll want this version.

Paul Graham – Beating the averages

Recently, having been prodded sufficiently by fellow enthusiasts, I’d been looking into the rationale behind Clojure amidst the ongoing explosion of dynamic languages on the jvm. And while I was looking into that, somehow, I came across numerous sites linking to the essay by Paul Graham – Beating the averages. Today I finished reading it and I have to say it was a fascinating, captivating and thought provoking read. Paul Graham is an adept writer. Yes I’m late to this scene. I’ve never really paid much attention to his essays in the past but I guess I’m finding myself going back in time in some ways now.

Also being one of the most persuasive pieces of prose speaking in favour of a language I’ve ever read – it made me incredibly curious about Lisp of which Clojure is a derivative. I think, at this stage, simply as a result of having read that post, there is a real danger of me looking into Lisp along the way which, if nothing else, should at least give me some insight into why the jvm developers Joe Darcy, John Rose and Mark Reinhold have been so enamoured with it and why they take so much inspiration from it.

The Java 7 launch party videos also made numerous mentions of Scala and Clojure which you watch if you haven’t already. The Q&A video at the end is the one I’m referring to here but I’d recommend watching them all in order. Anyway, you should read Paul Graham’s essay simply to provoke thought if for no other reason.

If you’re an avid Paul Graham follower which essay is your favourite that you’d recommend?

Installing Java, Scala and Vim support on Linux

Here’s a quick guide on how to install Scala on linux (in my case Ubuntu 9.04). A prerequisite obviously is to have the sun jdk installed and properly integrated into your linux environment. For completeness I detail how I normally tend to set up the jdk on my linux environment before moving onto the installation of Scala. Note that here /opt/ is used as the destination directory for installation as that is what I prefer but this can be any directory that you have write permissions on. You’ll also note that I don’t use any automated linux installation tool like apt-get and that is deliberate as the following methods of installation allow you not only complete control of installation of the packages but greater flexibility when upgrading. Finally we’ll look at adding Scala support to my favourite command line editor – Vim.

Install Sun JDK

Download the latest Sun JDK (JDK 6 Update 14 at time of writing).

Make executable and extract.

$ chmod u+x jdk-6u14-linux-i586.bin
$ ./jdk-6u14-linux-i586.bin

Relocate.

$ mv jdk1.6.0_14/ /opt/

Symlink.

$ cd /opt/
$ ln -s jdk1.6.0_14/ java

In /etc/profile set JAVA_HOME variable and add JDK bin directory to system path.

export JAVA_HOME="/opt/java"
export PATH="${JAVA_HOME}/bin:${PATH}"

Import your newly modified profile

$ source /etc/profile

Test Java.

$ java -version
java version "1.6.0_14"
Java(TM) SE Runtime Environment (build 1.6.0_14-b08)
Java HotSpot(TM) Server VM (build 14.0-b16, mixed mode)
$ javac -version
javac 1.6.0_14

Install Scala

Download the latest Scala (2.7.5 at time of writing).

Extract.

$ tar -xvzf scala-2.7.5.final.tgz

Move.

$ mv scala-2.7.5.final/ /opt/

Symlink.

$ cd /opt/
$ ln -s scala-2.7.5.final/ scala

In /etc/profile set SCALA_HOME environment variable and add the Scala bin directory to your system path.

export SCALA_HOME="/opt/scala"
export PATH="${SCALA_HOME}/bin:${JAVA_HOME}/bin:${PATH}"

Import your newly modified profile

$ source /etc/profile

Test Scala.

$ scala
Welcome to Scala version 2.7.5.final (Java HotSpot(TM) Server VM, Java 1.6.0_14).
Type in expressions to have them evaluated.
Type :help for more information.

scala> 1+1
res0: Int = 2

scala> println("Hello World!")
Hello World!

Add Scala support into Vim

If you’re like me and you can’t live without Vim or you just need Vim to get started with Scala prior to moving onto your favourite IDE then here’s how you can add Scala support into Vim.

Create required vim directories.

$ mkdir -pv ~/.vim/ftdetect
$ mkdir -pv ~/.vim/indent
$ mkdir -pv ~/.vim/syntax

Download Scala support into vim directories.

$ wget --no-check-certificate https://lampsvn.epfl.ch/trac/scala/export/18260/scala-tool-support/trunk/src/vim/ftdetect/scala.vim -O ~/.vim/ftdetect/scala.vim
$ wget --no-check-certificate https://lampsvn.epfl.ch/trac/scala/export/18260/scala-tool-support/trunk/src/vim/indent/scala.vim -O ~/.vim/indent/scala.vim
$ wget --no-check-certificate https://lampsvn.epfl.ch/trac/scala/export/18260/scala-tool-support/trunk/src/vim/syntax/scala.vim -O ~/.vim/syntax/scala.vim

Create a basic ~/.vimrc configuration if you haven’t got one.

set nocompatible
set nu  
syntax on
filetype indent on
set autoindent
set ic
set hls 
set lbr 
colorscheme delek

Try editing a Scala file. It should appear in colour.

1 for {i <- 1 to 10
2 j <- 1 to 10}
3 println(i*j)

Rejoice. Get coffee. Develop. Lose sleep. The usual lifecycle.

Acknowledgements (Scala Vim support, Vim colorised output).