Roman Numeral parsing in Haskell
================================

Copyright 2006-2010 Ben Clifford. Based on Java code by the same author
developed sometime around 2000. Licensed under a BSD-like license.

This document is literate haskell - you can download it and run it, like this:

$ wget http://www.hawaga.org.uk/ben/tech/Hrn.lhs
$ ghc Hrn.lhs 
$ ./a.out MCM XXX XIX VI V MCMXCVII
[1900,30,19,6,5,1997]
get http://www.hawaga.org.uk/ben/tech/Hrn.lhs

or you can read it (which you are doing now).

> import System.Environment

Each Roman numeral has a specific value:

> numerals = [ 
>    ('I', 1),
>    ('V', 5),
>    ('X', 10),
>    ('L', 50),
>    ('C', 100),
>    ('D', 500),
>    ('M', 1000)
>   ]

Given a string of characters (eg. "MMIV") we can easily map this
to a list of corresponding integers (eg. [1000, 1000, 1, 5]).

> numeralsToIntegers s = map numeralToInteger s

To do this, we make use of the numeralToInteger helper function, which
looks up a single numeral in the numerals table. If the numeral 
doesn't exist, it throws an error.

> numeralToInteger c = let 
>   r = lookup c numerals in
>   case r of 
>     Nothing -> error ("Unknown roman numeral: "++[c])
>     Just x -> x

The basic algorithm is simply to sum the digits.  However, this does not 
fully support the style of writing that is common in the latter day.  It 
can handle (for example) III or MMX, but not VI or MCM.

> numeralsToIntegerAdditive s = foldl1 (+) (numeralsToIntegers s)

To handle the full range of inputs, we need to check whether a 
large number is preceeded by a smaller number, and in this case perform
a subtraction. In other cases, perform an addition as before. 

> numeralsToIntegerSubtractive s = foldr (+-) (0,0) (numeralsToIntegers s)

This code makes use of the +- operator, defined here. It passes the value
of the last processed digit from right to left as the second element
of a pair.

> preceeding +- (sum,succeeding) =
>   if preceeding>=succeeding
>     then (sum+preceeding,preceeding)
>     else (sum-preceeding,preceeding)

To extract the final value, we can get the accumulator from the returned
pair and discard the last processed digit (which will be the first
digit of our roman numeral string).

> numeralsToInteger s = let (x,_) = (numeralsToIntegerSubtractive s) in x



Now all we need is a simple main routine to drive it all.

> main = do 
>   args <- getArgs
>   print $ map numeralsToInteger args