data RN = Null | I | V | X | L | C | D | M
	  deriving (Eq, Ord, Enum, Show)
                   
rnval :: RN -> Integer
rnval Null = 0 -- represents 'no numeral'
rnval I = 1
rnval V = 5
rnval X = 10
rnval L = 50
rnval C = 100
rnval D = 500
rnval M = 1000
          
nextsmallestrn :: RN -> RN			
nextsmallestrn Null = Null
nextsmallestrn x = toEnum (fromEnum x - 1)
                   
rntoan :: [RN] -> Integer
rntoan [] = 0
rntoan [x] = rnval x
rntoan (x1:x2:xs) = if x1 < x2 then
                    rnval x2 - rnval x1 + (rntoan xs)
                    else
                    rnval x1 + (rntoan (x2:xs))
                                
antorn :: Integer -> [RN]
antorn 0 = []
-- compute the first one or two roman numerals, and recursively
-- determine the rest
antorn x = (prefix ++ base) ++ (antorn remainder) where
	   chosenpair = fst (largestrn x)
           chosenpairvalue = snd (largestrn x)
	   prefix = if (fst chosenpair == Null) then [] else [(fst chosenpair)]
	   base = [snd chosenpair]
	   remainder = x - chosenpairvalue
                       
-- largest pair of roman numerals we can choose to be at the start of 
-- a list of roman numerals with value equal to x. If the base should have no 
-- subtracting prefix, the prefix will be Null
largestrn :: Integer -> ((RN, RN), Integer)
largestrn x = (rnpair, value) where
              -- choose the largest from a filtered list of all possible 
              -- prefixes
              rnpair = largestinrnlist 
	               [(prefix, base) | prefix <- prefixrns, base <- allrns,
                       -- rule 1: only subtract from a base numeral when the
                       -- result of the subtraction is larger than the next 
                       -- smallest denomination after the base numeral; i.e.,
                       -- (V,X) is illegal
                        (rnval base - rnval prefix) > 
                        rnval (nextsmallestrn base),
                        -- rule 2: the value of the pair of numerals must be 
                        -- less than x (subsequent numerals after the pair can 
                        -- only increase the value)
	                rnval base - rnval prefix <= x,
                        -- rule 3: a prefix must have a value no less than 
                        -- 1/10th of the base
	                (prefix == Null || rnval prefix >= x `div` 10)]
              value = rnval (snd rnpair) - rnval (fst rnpair)
	      allrns = [x | x <- enumFrom Null] -- set of all roman numerals
	      prefixrns = [I, X, C, Null] -- set of all legal prefixes
                                           

-- the largest pair of roman numerals in a list
largestinrnlist :: [(RN,RN)] -> (RN, RN)
largestinrnlist [x] = x
largestinrnlist (x:xs) = largerrn x (largestinrnlist xs)
                         
-- the larger of a pair of roman numerals
largerrn :: (RN, RN) -> (RN, RN) -> (RN, RN)
largerrn (x1, y1) (x2, y2) = if rnval y1 - rnval x1 > rnval y2 - rnval x2 then 
			    (x1, y1)
			    else
			    (x2, y2)