onsdag 21 juli 2010

Roman Numerals Kata in Scala

I got back to work monday this week after roughly 12 month of parental leave (Sweden has some awesome benefits). Since the office is realy quite and I am sitting idle with no assignment I figured that I would spend my time doing some Katas in Scala. At the last Scala Meetup in Gothenburg (which I unfortunately missed) they did the Roman Numerals Kata and I figured I'd implement that to start. I have decided to go back to basics with my coding after tiering of Eclipse going real sluggish for the umphteenth time and as such I have installed emacs once again. There is a basic scala-mode for emacs that is distributed with the Scala release and there is also an compliment to it named Ensime that is under development and adds some nice features, such as code completion, sbt integration, inspection of types, etc etc. So after installing emacs, Scala, Ensime and SBT (Simple Build Tool) I started on the kata.

I usually like to start out writing tests for my code and Specs provides a pretty nice DSL way to do that. Here is the tests for my ArabicRomanConverter:

All in all pretty simple tests for border cases, the different simple cases along with a few randomly chosen numbers. Onward to the implementation code!

Here the apply function takes care of my input sanity checks, verifying that the number is actually convertable to roman numbers (at least to the roman numbers of the magnitude I am interested in). The listOfPairs is used in the convert method below.

In the convert function I have defined an recursive function called innerLoop and annoted it with @tailrec. The annotation tells the compiler to optimize the function to a loop and gives an error if the function is not tail recursive. The innerLoop is tail recursive because the last opperation in the function is a call to itself or the return value for the function as a whole.

So what does the innerLoop actually do? Well it starts out by checking if we are done and should return the StringBuilder-Num-Counter-tuple by verifying that "num", "count", the int in the "rPair" tuple are all greater than 0 (basically just a precaution). It also checks if it is "safe" to subtract the integer in the "rPair" tuple from "num". Then if the "count" is greater than "num", "count" should be decremented by the integer in the "rPair" tuple, otherwise "num" should be decremented and the String in the "rPair" tuple appended to the StringBuilder. In both cases we do a recursive call to innerLoop and try again. The innerLoop function gets called from within the foldLeft over the "listOfPairs". So basically for each romanNumPair we attempt to subtract the integer in the pair from the "num" (in the innerLoop) as many times as possible (and still keeping "num" greater than or equal to 0). The StringBuilder is then extracted from the result of the foldLeft and converted to a String.

Having completed the kata I started to ponder if there isn't a better way. The roman numbers aren't actually Strings but Numbers and it would be cool if you could add, subtract, multiply and divide them as such. So I have decided to check if there is an easy and clean way to do this in Scala... more on that another time perhaps.

1 kommentar:

  1. See my implementation of Roman Kata in immutable Scala