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
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\$