Fun Friday – Roman Numeral Kata

Roman numerals are about the most useless things on the planet nowadays, provided you aren’t rolling credits at a movie screen.

However, if the Romans DO return, we have a solution to the pesky number problem. I present you my F# implementation.

I endeavor to explain for those not yet converted to the F# happy-path.

The first lines (1-3), declares a value (“vals”) as a list of tuples. Those tuples consist of a number, and it’s equivalent textual value in the Roman Numeral form. The ordering is important, as it goes from largest numerical value to smallest in the list.

Both functions defined here (toRoman and fromRoman) are very similarly designed. They start with a single parameter, and then define and internal looping function that actually creates the resulting value. Then they call that internal function with an “empty” accumulator, the initial parameter value, and the vals list declared above. If you run a simple test in FSI with these functions you should easily get some good results:

> toRoman 54;;
val it : string = "LIV"

> toRoman 2017;;
val it : string = "MMXVII"

> fromRoman "MMXVII";;
val it : int = 2017

Internal loops with an accumulator are common in functional code. Our loops use the “acc” (aka, accumulator) parameter to sum up the matching numbers in the fromRoman function, and to build the resulting string in the toRoman function. The internal loop  matches the incoming list, and compares it against 3 possible options. The first possible match is against an empty list. If the list passed in to the loop function is empty, it simply returns the acc value. The second match is a list with the head of the element deconstructed as a tuple (i, s), filtering when the “n” parameter (of the loop function) is larger than (or equal to) the “i” value in the tuple. In that case, we simply call the loop function again, appending the s value to the acc parameter, subtracting the i value from the n parameter, and passing the same list into the function again. Finally the third option is when it’s just a simple list object that has a head and a tail (the match order counts) and it passes the existing acc and n parameter values to the loop function with the tail of the list.

When I pass in 54 into the toRoman function, the first thing that happens in that function is:

1) The loop function is defined and then called, with “” as the acc parameter, 54 as the n parameter and the vals list [(1000, “M”)…(1, “I”)] as the list parameter.

2) The loop executes, matching against the list parameter.

3) The list is not empty, so it skips the first match.

4) The first value in the list (1000, “M”) is capable of being represented as a tuple (i, s), and the list itself matches the cons operator (“::“) as well, but the “when” setting n >= i does NOT match, because the n parameter is 54 and the i is 1000, so it skips the second match.

* Reread and, make sure you understand this part, as it’s the critical point of the function.

5) The final option matches, and calls loop again, this time with parameters: acc = “”; n = 54, and list = [(900, “CM”)…(1, “I”)] 

6) The steps 3-5 execute again. The head of the list is compared, until eventually the “n” parameter is larger or equal to the corresponding “i” (from step 4).
(900, “CM”) -> Nope
(500, “D”) -> Nada
(400, “CD”) -> No Dice
…
…
(50, “L”) -> That’s a match!

7) Since that match occurred, we STILL loop through the execution, but now we modify our parameters a bit. Instead of the plain old acc, now we apply a function to the acc to accumulate the value; acc is no longer “”, it is now “” + “L”.  The variable n is modified as well. It is no longer 54, it becomes 4 (54 – 50). The list value stays the same [(50,”L”)…(1, “I”)].

8) The new values are now matched, and the process continues. The list is still not empty, and the new n value (4) is clearly less than 50 (the first element in the list), so we move on through the list, in the same way we did before but against the new n value (4):
(50, “L”) -> Nope
(40, “XL”) -> Negative
(10, “X”) -> No Dice
(9, “IX”) -> Sorry
(5, “V”) -> Not quite
(4, “IV”) -> Yep!

9) The result updates acc to “LIV”, and n to 0. We loop through the remaining 2 items in the list (4, “IV”) and (1, “I”) and get to the last possible match [], the empty list.  The last match returns the acc passed in (“LIV”). That becomes our final value, and is the result of our toRoman function.

The differences between fromRoman and toRoman are simply related to the data types involved. String “subtraction” doesn’t work with a simple minus sign (at least, not without defining a new infix operator), so instead it’s “str.Substring(s.Length).” String comparison doesn’t work with the >= operator, so str.StartsWith(s) was recruited to do the job. Everything else largely works the same, the accumulator accumulates the values while the function executes and the str variable is “decremented”, until the list is exhausted.

There are some clear flaws in my implementations here, and I accept them for what they are. Firstly, in the toRoman function, negative value parameters all return an empty string. I don’t remember my mathematics history there, and I am not sure if they even actually had the concept of negative numbers back then. If you are a history buff, and know the answer, please comment and let me know. Secondly, the fromRoman function isn’t validating the incoming text. You could submit something things like “CDCDCD”, and it would return 1200, even though the input is clearly wrong. Finally, when you put in an exceptionally large number into toRoman, you can end up with a LOT of “M”s, simply because the vals list doesn’t contain enough “domain knowledge” about larger numbers.

Still, it largely works, so for a Fun Friday, I’m happy with it. Enjoy!