Implementing Type Safe Roman Numerals in Scala (type parameter extravaganza!)

I figured I wanted to do some more stuff with the roman numerals and try and create a type safe way to count with them (integers are so 2000 were living in the MMX now ;-)). Anyway what I wanted was something that could be used to express roman numerals in source files and that the compiler would say no if I expressed them in a flawed manner. It should be possible to write something like: MM I (1001), but it should not be possible to write: I MM (since that is not a proper roman numeral).

I started out with a lass in Scala:


Then using some traits I could add the ability to express simple combinations of roman numerals:


After importing the RomanNumeral class and the traits along with the contents of the RomanNumerals object I was able to write M CD since scala interprets that as M.CD and since M (defined in the RomanNumerals object) extends the NumeralM trait it has a method CD. It would also not be possible to write I M since I only extends the trait NumeralI which does not define any M method. This is all well and good, but I wanted some more expressive power. I wanted to be able to write something along the lines of M CM X I (i.e. 1911), but that is not possible because the way scala interprets spaces M CM X I would be turned into: M.CM(X).I . That means my RomanNumeral would need an apply method that could take another RomanNumeral and return a new one. So I defined one:



Now atleast I was able to write M CM X (since that is "M.CM(X)") however I was also able to write M CM M (i.e. M.CM(M)), but that would be an illegal RomanNumeral (since the M CM is 1900 it doesn't make sense to have an M after it; L, X, V, I would all be valid but not M nor C). In addition I was not able to write M CM X I since the returned RomanNumeral from the apply method had no NumeralN mixed in when instantiated (using with). I would be able to write M.CM.X.I since that indicates to the compiler that I am calling a method on the return value of the previous method (i.e. calling the method X on the return value of the method CM and so on), but I wanted to do this without the dots :).

So first things first; how could I know in th eapply method which trait I should mixin with the returned RomanNumeral so that it would have the appropriate methods available? Enter the type parameters. I first tried redefining the RomanNumeral class as follows:



However that does not work. Why you ask? Well, first some explanation of the type parameters introduced. The type parameters for the RomanNumeral is specified with T<:Numeral the <:Numeral part is a upper bound on the type that can be used for the class. So instantiating a RomanNumeral I would atleast have to pass in a Numeral or a subclass thereof. In the apply method I specify an upper and a lower bounds for the type parameter of the RomanNumeral passed in as an argument to the method. The lower bounds on the type parameter is T and the upper bound is Numeral so the type used as a type parameter of the RomanNumeral being passed to the method has to atleast be a Numeral and at most be a T (which in turn has to be a subtype of Numeral). A few examples in the interpreter might be helpfull here... (lets ignore the "with N" part of the code above)



Since NumeralI is a super class of NumeralV and a subclass of Numeral the "five" value can be supplied with the "three" value to its apply method. Doing the reverse causes a type missmatch since NumeralV is not a superclass of NumeralI. Method apply would look like this in the first instance (with the type parameters spelt out):



and in the latter case:



All this is a ok. So why doesn't the RomanNumeral code above compile? Well, because of type erasure for one and also because N could be a concrete class and not a trait(only traits can be mixed in to classes at instantiation time). After type erasure there is no way of knowing what N is and therefore the RomanNumeral class above would not compile. At this point I tried alot of different version of the above to find something which did work. In the end I realized that I could have an apply method that took a NumeralN instead and have one for each trait. That way I would know which type should be mixed in with the RomanNumeral.



This worked fine, but allowed any Numeral to follow any other. Using the interpreter to illustrate:



As can be seen above a NumeralI could be followed by a NumeralV which should not be allowed. By changing the NumeralI and its subtypes to take a type parameter I was able to add the type bounds back to the apply methods and enforce the correct behaviour. The traits now looks like this:



And the RomanNumeral class looks like:



With these modifications I could now specify the values in ther RomanNumerals object as follows:



By importing all the classes and traits and then importing the contents of the RomanNumerals object (import RomanNumerals._) I can now write my roman numerals in a type safe way. I.e. M C X V I (which is equivalent of writing: M.C.apply(X).V.apply(I) ) is allowed but M CM C is not allowed. Why? Well, since the return value of the CM method is a RomanNumeral with the type parameters NumeralL[Numeral] (and with NumeralL[Numeral] mixed in) the apply methods all look like:

and C has the type RomanNumeral[NumeralC[Numeral]] with NumeralC[Numeral] there is no apply method where C is a valid argument (C is a NumeralC[Numeral] which is a subtype of NumeralL[Numeral] and as such violates the lower bounds on the type parameter).

Next I created a rollover so that when a RomanNumeral is created that is larger than 3999 it rolls over to a number which can be described with roman numerals (i.e. > 0 and < 4000). Then to wrapp things up I simply added a companion object with an apply/unapply method to my RomanNumeral so it can easily be used in pattern matching. I also added some methods for basic arithmatic (+-/*), implemented the Ordered trait and extended the Number class. Finally I added an implicit conversion from Number to a RomanNumeral[Numeral] so that I could add Integers and Doubles and such to a RomanNumeral and vice versa (with a result type of a RomanNumeral[Numeral]).

The final result can be seen below (now I only need to find a problem for my solution :-) ):

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.