For some reason, I suddenly felt like playing around with Scala for a couple of days, and having gotten over my perceived difficulty of the language vs Groovy, and after actually trying to write something in it – I really like it 🙂
At first glance, advanced functional programming in Scala can look a little freaky to someone who’s only been writing Java for the last few years. But if you start slowly, it all slides into place. I started to get into it by reading this is a really good series of articles introducing the language
What follows are two examples of Scala. The first, LoveGame is a demonstration of programming a simple algorithm in Scala along with a little comarpison with Java. The second is a little toying around i did with Scala to create a front end for JScience with the “Pimp my library” pattern.
The Loooove Game
I’m teaching a course to our new hires in Melbourne at the moment and one of their assignments was to write a program called “Love Game” which implemented a simple algorithm to calculate the compatibility between two people based on the letters in their names. I’m sure you all remember doing this as a kid?
Well, in the weekend, I couldn’t help but start thinking about how the algorithm could be expressed so much better. So I thought this was the motivation to give Scala another shot.
The algorithm in java looks like this:
// Creates 2 character arrays that will be compared
char bothNamesArray[] = "roger federer maria sharapova".toCharArray();
char compWordArray[] = "loves".toCharArray();
// Creates an Integer array for storing count results
Integer tallyArray[] = new Integer[compWord.length()];
int tallyArrayPointer = 0;
int matchCounter = 0;
/*
 * Counts the number of times each character in compWordArray also
 * appears in bothNamesArray
 */
while (tallyArrayPointer < compWord.length()) {
 for (int i = 0; i < bothNames.length(); i++) {
 char nameLetter = bothNamesArray[i];
 char compLetter = compWordArray[tallyArrayPointer];
if (nameLetter == compLetter) {
 matchCounter++;
 }
tallyArray[tallyArrayPointer] = matchCounter;
 }
matchCounter = 0;
 tallyArrayPointer++;
}
int tallyCounter;
int totalAdder;
/*
 * Calculates the compatibility percentage by adding consecutive
 * numbers in tallyArray together.
 */
while (tallyArray[2] != -1) {
 tallyCounter = 0;
while ((tallyCounter < tallyArray.length - 1)
 && (tallyArray[tallyCounter + 1] != -1)) {
 totalAdder = tallyArray[tallyCounter]
 + tallyArray[tallyCounter + 1];
 tallyArray[tallyCounter] = totalAdder;
 tallyCounter++;
 }
tallyArray[tallyCounter] = -1;
}
int finalPercentage = (tallyArray[0] + tallyArray[1]) * 2;
// Displays the compatibility percentage
System.out.println("\nCalculated compatibility = " + finalPercentage + " %" );[/sourcecode]
<pre>NB: Yes we could re-write the Java implementation using recursion also, but it doesn’t fit as nicely as it does into the Scala solution, and the Java code would still require most of it’s verbosity.</pre>
It works in two steps;
<ol>
<li>Counts the frequency of occurrence of the letters in the word love, in the full names</li>
<li>Takes this list of frequencies and reduces it down to one number by adding up pairs of values in the list, creating a new list, then repeating until there’s one value left. That value is then multiplied by two, and that’s your result.</li>
</ol>
This is what the Scala code to do the same thing looks like:
I can't stop sitting here and steering at how awesomely terse the following Scala code really is....
val names = "roger federer maria sharapova"
val initialList = "loves".toList map( x => names.toList count(x == _ ))
def loveReduce(numbers:List[Int]):Int = numbers match {
 case head :: Nil => head * 2
 case _ => loveReduce(numbers zip(numbers tail) map {case (a, b) => a+b})
}
// Displays the compatibility percentage
println("Compatibility = " + loveReduce(initialList) + " %" )
As you can see, the algorithm can be written in far fewer lines of code, and is far simpler to understand, expecially the second stage. This means it’s much easier to see that it is correct.Ironically, the Java code above actually fails in the case where the “verb” (loves), is replaced with a smaller work like “is”. There may also be other cases where it fails. However the Scala code works perfectly!
Step One
"loves".map( x => names.count( y => x == y ))
NB: toList() has been removed for clarity.
The first step is to find our list of frequencies.
List.map()
What the map fuction does, is apply a given function F(x) to a list of elements, returning a new list, such that each element is now the result of F(x).
For example:
Consider the array
[1,2,3,4]
Applying map(F(x)) results in:
[F(1),F(2),F(3),F(4)].
If we imagine the function we pass is F(x) = x+1, then the returned array would look like:
[2,3,4,5]
In our code, we have defined our function F(x) to be the number of times our x appears in the String names. We do that by using the count() function.
List.count()
The count function counts the number of elements in a list which satisfy a given condition. We pass that ‘condition’ in as a function. In our case, we are breaking up the word loves into individual letters, so we want to count how many times that letter occurs in the names string.
By using the count function, we iterate through the names string, letter by letter, counting the times a given letter in the name – y – equals the letter we access from our outer loop – x. We then perform the same operation, but with the next letter in the word loves.
In our code above, you can see we are passing the function x == y ( x == _ is short hand). Again, where x is a letter in the word loves and y is a letter in the names. Note that this one line is an O(n^2) complexity.
Step Two
def loveReduce(numbers:List[Int]):Int = numbers match {
 case head :: Nil => head * 2
 case _ => loveReduce(numbers.zip(numbers.tail).map{case (a, b) => a+b})
}
Ignore the method signature at this point, let’s explain the algorithm.The second part in the algorithm deals with the list of frequencies. For the example “Roger Federer loves Maria Sharapova”, the frequency count for the letters in the loves is:List(0, 2, 1, 4, 1)We then to add up each pair of numbers to create a new array e.g. List(2, 3, 5, 5) and repeat until are left with a single element which we multiply by 2.To express this very tersely, in Scala, recursion is involved. We could re-write the Java implementation using recursion also, but it doesn’t fit as nicely as it does into the Scala solution, and the Java code would still require most of it’s verbosity.
The list gets reduced as so:
List(0, 2, 1, 4, 1)
List(2, 3, 5, 5)
List(5, 8, 10)
List(13, 18)
List(31)
Apart from the pattern matching (we’ll get to that soon), most of this method is similar to how you would do it in Java. The really interesting Scala part of this example is this line:
numbers.zip(numbers.tail).map{case (a, b) => a+b}
What this is doing is constructing a list of tuples (pretty much two element arrays) by combining two lists, and then applying another map function, the function being adding together the two elements in the tuple.numbers.tail returns the list without it head (with out it’s first element). So we are effectively calling:[ 1 , 2 , 3 , 4 ] . zip( [ 2 , 3 , 4 ] ) The result of this call is a list which looks like;
List((1,2), (2,3), (3,4))
It is one element shorter than the original list because the zip() is defined such that when zipping together lists of different length, remaining elements in the longer list are ignored.
We then apply the map() function to this array of tuples, with the function F( case (a,b) => a+b). The case statement uses Scala pattern matching to retreive a matchin tuple element. The result from this is now the tuples all added together, and the list one element shorter:
List(3, 5, 7)
Then we simply recursively call the loveReduce method again on the newlist.
numbers match {
 case head :: Nil => head * 2
 case _ => loveReduce(...)
}
This is similar in nature to Java’s switch statement, but far, far more powerful. It uses a powerful concept called pattern matching and is not simply restricted to either ints or enums.In our example, we are performing a math on our numbers list where our first case is the end of recursion. This being where the parameter passed in as number, matches a list (as Scala knows it’s a list) where the list has only a head element and nothing else (one element in the list). The statement which would match a list which had two or more elements would be “head :: tail“.The reason we don’t need to return from a case is that in Scala, unlike Java, cases do not overflow into each other, so to end or recursion, we simply return the head element, multiplied by two, as per our LoveGame algorithm.The second case uses the universal operator “_” which is used in several places in Scala, but used consistently. This is similar to the “default” case in Java. In this case, we want to perform our zip and map, and make our recursive call again.And to breiflly explain the method signature of loveReduce
def loveReduce(numbers:List[Int]):Int
In Scala, everything is an object, even functions. Above we define the loveReduce function. It takes one parameter called numbers of type List[Int]. As you can see Scala supports type parameters, just like Java’s Generics. Usually, in Scala, returns types of a method can be inferred by it’s type inference system. However, there are cases where the return type of the method has to be specified and this is one. But don’t worry – the compiler will tell you when you need to! Here we simply define the return type of the method is Int.On a side note – in Scala, everything is an object – even simple ints. So unlike in Java where auto-boxing was introduced in 1.5, Scala treats all simple numbers as Objects.
Engineering
That is the compact version of the code. Originally I wrote it in a more engineered way, in order to learn more Scala, and also so that I could learn more about implicit conversions.
/**
 * LoveGame algorithm. Uses a recursive function to reduce the frequency
 * list to the final result.
 */
class LoveGame(verb:String) extends MyConversions {
/** Reduces a list of numbers down to a single number by continually
 * adding up consecutive pairs until there is only one element left,
 * and multiplies it by one. */
 def loveReduce(numbers:List[Int]):Int = numbers match {
 case head :: Nil => head * 2
 case _ => loveReduce(numbers.zip(numbers.tail).map{case (a, b) => a+b})
 }
/** Runs the LoveGame on the words in the String names based on
 * the class parameter verb.
 */
 def compute(names:String):Int = {
 val initialList = verb.toLowerCase.countOccurances(names.toLowerCase)
 loveReduce(initialList)
 }
}
/**
 * A collection of implicit conversions used in this component.
 */
trait MyConversions {
 implicit def string2MyRichString(str:String) = new MyRichString(str)
}
/**
 * Pimps out the String class with extra methods.
 */
class MyRichString(str:String) {
 /** Counts the frequency each letter in occures _haystack_, returning a list. */
 def countOccurances(haystack:String) =
 str.toList.map( x => haystack.toList.count(x == _ ))
}
/**
 * Bootstrap for the LoveGame program. Should be replaced by a xUnit test.
 */
object LoveGameProgram extends Application {
 val names = Array( "Roger","Federer","Maria","Sharapova" ).mkString( " " ) // loves - 62%
 val loveGame = new LoveGame( "loves" )
 println(names)
 println( "Compatibility = " + loveGame.compute(names.mkString( " " )) + " %" )
}
Update:
Inspired by my friends C# code below, here’s the love game in Scala again, but using the while loop approach in 4 lines (i.e. minus pattern matching, recursion and functions):
 var loves = "loves".toList map( x => "roger federer maria sharapova".toList count(x == _ ))
 while (loves.length > 1)
 loves = loves zip(loves tail) map {case (a, b) => a+b}
 println( "3 line compatibility = " + loves.head * 2 + " % " )
Pimp My Library
In honor of this JScience and Groovy example, here’s something in Scala going for the same sort of thing – extrapolate out, use your imagination.
For those of you who don’t know what JScience is: “JScience is a comprehensive Java library for the scientific community.
Its vision is to create synergy between all sciences (mathematics, physics, sociology, biology, astronomy, economics, geography, history, etc.) by integrating them into a single architecture.”
It is also going to be the in Java soon as the Reference Implementation (RI) for JSR-275: javax.measure.* (Latest Draft Specification).
It allows you to do stuff like this in Java:
Measure length = Measure.valueOf(50, SI.CENTI(SI.METER)).plus(Measure.valueOf(25.0, SI.METER));
Measure lengthInCentimeters = length.to(SI.CENTI(SI.METER));
System.out.println("length in centimeters is " + lengthInCentimeters.getEstimatedValue());
But that’s pretty verbose, wouldn’t you rather just write:
var len = 50.centimeters + 25.meters
println("length in centimeters is " + len)
Well, below is the start of writing a wrapper for the JScience Library using Scala’s implicit conversions.
println(2.miles.to.meters)
class MyInt(quantity: Int) {
 def miles() = new Mile(quantity)
 def mile() = new Mile(quantity)
}
abstract class Measure {
 def to() = new Converter(this)
 def toMeters()
}
class Mile(quantity: Int) extends Measure {
 def conversionFactorToMeters:Double = 1.609344 * 1000;
 override def toMeters() = quantity * conversionFactorToMeters
}
class Feet(quantity: Int) extends Measure {
 def conversionFactorToMeters = 1/0.3048
 override def toMeters = quantity * conversionFactorToMeters
}
class Converter(quantity: Measure) {
 def meters() = quantity.toMeters()
}
implicit def numberToMile(number:Int) = new MyInt(number)
How powerful is that? Implicit conversions allow the “Pimp my library” pattern which can be really powerful. I certainly know it would have been really useful in my last project!P.S. If anyone knows anything about Scala code high lighting in hosted WordPress drop me a line! Sourcode tag doesn’t support it.
Stubbisms - Tony's Weblog 