5
\$\begingroup\$

I have written a module that provides some functions for dealing with Roman numerals. I would like some feedback concerning my style, potential performance or elegance improvements, and any suggestions for additional functions to add.

In particular, I would like to know if there is a clever way to simplify the functions subtractive, additive, and isValid. I would like to know if using -XFlexibleInstances and -XOverlappingInstances to create an instance of Show for type Numeral is considered good or bad practice, and if there's an elegant way to do without them. I would also like to know about the interface with the module, do you think I am exporting too many functions, or not enough?

{-
file:   RomanNumerals.hs 
title:  Roman Numerals
date:   pridie Idus Februarius, A.D. MMXVI 

description:
        Provides functions for converting between Roman numerals and
    integers, checking if a Roman numeral is valid, and reducing a
    Roman numeral to its minimal form.

license:
        GNU General Public License version III
        <http://www.gnu.org/licenses/gpl-3.0.en.html>

references:
        Wikipedia - Roman numerals
        <https://en.wikipedia.org/wiki/Roman_numerals>
        Project Euler - About... Roman numerals
        <https://projecteuler.net/about=roman_numerals>
-}

{-# LANGUAGE FlexibleInstances    #-}
{-# LANGUAGE OverlappingInstances #-}

module RomanNumerals
( Numeral
, numeralFromString
, numeralToString
, numeralFromInt
, numeralToInt
, isValid
, minimal
, additive
, subtractive
) where

import Data.Maybe (fromJust, isJust)
import Data.Tuple (swap)
import Data.List

data Symbol = I  -- 1
            | IV -- 4
            | V  -- 5
            | IX -- 9
            | X  -- 10
            | XL -- 40
            | L  -- 50
            | XC -- 90
            | C  -- 100
            | CD -- 400
            | D  -- 500
            | CM -- 900
            | M  -- 1000
    deriving (Show, Read, Eq, Ord)

type Numeral = [Symbol]

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

-- <http://stackoverflow.com/a/6000818/2738025>
instance Enum Symbol where
  fromEnum = fromJust . flip lookup symbolTable
  toEnum   = fromJust . flip lookup (map swap symbolTable)

-- Requires FlexibleInstances and OverlappingInstances to work.
instance Show Numeral where
  show = numeralToString

instance Read Numeral where
  readsPrec _ cs = [(numeralFromString cs, "")]

instance Enum Numeral where
  succ     = toEnum . succ . fromEnum
  pred     = toEnum . pred . fromEnum
  toEnum   = numeralFromInt
  fromEnum = numeralToInt

numeralFromString :: String -> Numeral
numeralFromString = subtractive . map (read . (:[]))

numeralToString :: Numeral -> String
numeralToString = concatMap show

numeralFromInt :: Int -> Numeral
numeralFromInt 0 = []
numeralFromInt i = s : numeralFromInt (i - fromEnum s)
  where
    s = fst $ last $ takeWhile ((<= i) . snd) symbolTable  

numeralToInt :: Numeral -> Int
numeralToInt = sum . map fromEnum

-- Converts a numeral into minimal form.
minimal :: Numeral -> Numeral
minimal = toEnum . fromEnum . subtractive

-- Converts a numeral from subtractive into additive form.
additive :: Numeral -> Numeral
additive []     = []
additive (s:ss) = case s of
    IV -> I : V : additive ss
    IX -> I : X : additive ss
    XL -> X : L : additive ss
    XC -> X : C : additive ss
    CD -> C : D : additive ss
    CM -> C : M : additive ss
    _  -> s : additive ss

-- Converts a numeral into subtractive form.
subtractive :: Numeral -> Numeral
subtractive []        = []
subtractive [s]       = [s]
subtractive (s:s':ss) = case (s, s') of
    (I, V) -> IV : subtractive ss
    (I, X) -> IX : subtractive ss
    (X, L) -> XL : subtractive ss
    (X, C) -> XC : subtractive ss
    (C, D) -> CD : subtractive ss
    (C, M) -> CM : subtractive ss
    _      -> s  : subtractive (s':ss)

-- Checks if a numeral is valid.
isValid :: Numeral -> Bool
isValid n = descending (subtractive n) && validCounts
  where
    validCounts = count D <= 1
               && count L <= 1
               && count V <= 1
               && fromEnum X > fromEnum V * count V 
                             + fromEnum I * count I
               && fromEnum C > fromEnum L * count L
                             + fromEnum X * count X
                             + fromEnum V * count V 
                             + fromEnum I * count I
               && fromEnum M > fromEnum D * count D
                             + fromEnum C * count C
                             + fromEnum L * count L
                             + fromEnum X * count X
                             + fromEnum V * count V 
                             + fromEnum I * count I
    count s = (\x -> if isJust x then fromJust x else 0) 
            $ lookup s $ frequencies (additive n)

-- <http://stackoverflow.com/a/30633116/2738025>
descending :: (Ord a, Eq a) => [a] -> Bool
descending []        = True
descending [s]       = True
descending (s:s':ss) = s >= s' && descending (s':ss) 

-- <http://stackoverflow.com/a/10398874/2738025>
frequencies :: Ord a => [a] -> [(a, Int)] 
frequencies = map (\l -> (head l, length l)) . group . sort
\$\endgroup\$
  • \$\begingroup\$ Maybe I'm rusty - but isn't the additive of "IV" the numeral "IIII"? \$\endgroup\$ – bdecaf Feb 13 '16 at 11:45
  • \$\begingroup\$ I'm also a bit confused about the isValid section - the subtractives IX etc. are not treated there. \$\endgroup\$ – bdecaf Feb 13 '16 at 11:53
  • \$\begingroup\$ @bdecaf, you're right about the additive of IV being IIII. In my model, "additive" just means that split into individual tokens (I, V, X...). I think the additive function would be more useful and intuitive if it actually put the numeral in additive form. Instead of using the additive function in isValid, I could check character counts in a string. \$\endgroup\$ – castle-bravo Feb 13 '16 at 14:22
  • \$\begingroup\$ @bdecaf, Now that I think about it, I'm a little confused with the isValid function too. It has two main checks, one which works on the numeral with subtractives in it (descending), and the other which checks that X is not being made from 2 Vs or 10 Is which works on the tokenized numeral. Thing is, it yields true for a number like IVIII, which I I'm not sure if is valid or not. If it's not valid, and I don't think it is, then I need to improve that. \$\endgroup\$ – castle-bravo Feb 13 '16 at 14:36
  • \$\begingroup\$ I see. In that sense I don't think the additive form you use is wrong. but since the definition is say nonstandard - it might be worth documenting. I would consider to not export this function. \$\endgroup\$ – bdecaf Feb 15 '16 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.