Arabic-Roman Number Converter in Haskell (Part 1: Converting Arabic to Roman Numbers)

Introduction

The provided code snippet can be used to convert Arabic numbers to Roman numbers. Currently, numbers up to 3999 are supported. See #Using the code if you want to convert larger numbers.

Background

In a recent coding dojo in my company, we worked on creating a JavaScript function to convert Arabic numbers to Roman numbers (Original task: http://codingdojo.org/cgi-bin/index.pl?KataRomanNumerals).

To refresh my functional programming skills, I decided to write a solution for the problem in Haskell.

Using the Code

To test the code for yourself, simply download and extract the provided file and load the file or copy the code snippets to your own file (NOTE: In this case, you have to add 'import Data.Map' before the first line) as in ghci. Then just call the numToRoman function.

The approach we went for in the dojo, was to iterate over all the numbers in the input while getting its current power to get the next Roman literal to append to the result string. So given 513, we would first consider the number 500, which converts to D, then 10, which converts to X, and finally 3, which converts to III.

To represent all the required literals, I created the following dictionary/map:

romans :: Map Int [Char]
romans = fromList [(1,"I"), (4, "IV"), (5,"V"), 
(9, "IX"), (10,"X"), (40, "XL"), (50, "L"),
                  (90, "XC"), (100,"C"), (400, "CD"), 
                  (500, "D"), (900, "CM"), (1000, "M")]

NOTE: As a simplification for the subtraction rule (e.g. 40 becomes XL instead of XXXX), I also added combined numerals to the map for the numbers starting with 4 or 9. Currently numbers up to 3999 can be converted. To convert bigger numbers, just add the according literals. So the next step would be to add literals for 4000, 5000, 9000 and 10000.

To get the single digits, I added the following helper function:

digits :: Integral x => x -> [x]
digits 0 = []
digits x = digits (x `div` 10) ++ [x `mod` 10]

So calling digits 513 would return [5,1,3].

With this, we can now start the conversion process:

numToRoman :: Int -> [Char]
numToRoman x = resolveRoman digs (len-1)
               where
                   digs = digits x
                   len = length digs
                   replicateStr amount str = concat $ replicate amount str
                   resolveRoman xs l = 
                        if (l < 0) then ""
                        else (getNextLiteral (head xs) (10^l)) 
                              ++ (resolveRoman (drop 1 xs) (l-1))
                             where getNextLiteral x pwr = 
                                if (x < 1) then ""
                                else if (x < 4) then replicateStr x (romans ! (pwr))
                                else if (x > 5 && x < 9) then (romans ! (5*pwr)) 
                                         ++ replicateStr (x-5) (romans ! (pwr))
                                else romans ! (x*pwr)

At first, we declare the fields digs and len to hold our input (as array) and its length (for 312, digs = [3,1,2] and len = 3. We also define the replicateStr helper so we can easily replicate strings (e.g. replicateStr 2 "I" gives "II").

In the removeRoman function, we first check if the given length (which represents the power) is smaller than 0, in which case we want to finish execution. Otherwise, we calculate the next literal by the using getNextLiteral-function defined in the where-clause and recursiveley call it with the remaining array. So for 312, we first convert 300 to "CCC" and then append to it the result of converting 12 and so on (decrementing the length/power in every step until we reach 0).

The getNextLiteral function returns the next required literal depending on the value of the number and its power. For values below 1, we simply return "" (there is no 0 literal in Roman number system). For other numbers < 4, we call the replicateStr function so we get the required amount of literals, where the literal itself is determined by the power. So for the digit 3 and the power 2, we have to replicate "C" three times which gives "CCC". The other edge cases work accordingly.

Points of Interest

Concluding, it was a very fun and interesting assignment. Since I haven´t touched Haskell for a while, there probably exist more convenient and shorter solutions, so feel free to provide any hints or code snippets or ask questions :).

History

So far, I have only covered the conversion from Arabic to Roman numbers. In a few weeks, I plan to write another article to convert Roman to Arabic numbers too.