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\$
7
  • \$\begingroup\$ Maybe I'm rusty - but isn't the additive of "IV" the numeral "IIII"? \$\endgroup\$
    – bdecaf
    Commented Feb 13, 2016 at 11:45
  • \$\begingroup\$ I'm also a bit confused about the isValid section - the subtractives IX etc. are not treated there. \$\endgroup\$
    – bdecaf
    Commented Feb 13, 2016 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\$ Commented Feb 13, 2016 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\$ Commented Feb 13, 2016 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
    Commented Feb 15, 2016 at 11:06

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.