Exploring Haskell's type system - A Roman number type

July 26, 2013 in

Once in a while I need a break from my day-to-day job in C# land. Don't get me wrong, I like the language, but it doesn't cover all of my intellectual needs. More specifically, if I

  • Need some functional, imperfect chaos, which gets much done nonetheless, or in Scott Hanselman's words, if I want to do some assembly language, I go and visit JavaScript
  • Need purity, the most amazing compiler that ruthlessly cracks down on any typing (in the computing sense) error you do, the serenity of a perfect universe that simulates dirt only if it has to, then I visit Haskell.

This time it was Haskell's turn - the last time I delved into Haskell, I hadn't really touched its type system, only used those already in place. This time I wanted to rectify that.

Behold - the Roman number

module Roman where
import Data.List
atoms = [("M",1000),("CM",900),("D",500),("CD",400),("C",100),("XC",90),
("L",50),("XL",40),("X",10),("IX",9),("V",5),("IV",4),("I",1)]
data Roman = R String | RN Int
instance Show Roman where
show a = show $ romanToString a
instance Eq Roman where
(==) a b = romanToInt a == romanToInt b
instance Num Roman where
(+) x y = RN (romanToInt x + romanToInt y)
(-) x y = RN (romanToInt x - romanToInt y)
(*) x y = RN (romanToInt x * romanToInt y)
abs = RN . abs . romanToInt
fromInteger = RN . fromIntegral
signum = RN . signum . romanToInt
romanStringToInt :: String -> Int
romanStringToInt input = twoLetterSum + (singleLetter reduced)
where
twoLetterSum = sum $ map snd matchingTwoLetters
reduced = foldl (\\) input $ map fst matchingTwoLetters
matchingTwoLetters = [ (lt,num) |(lt,num) <- atoms, length lt == 2, isInfixOf lt input]
singleLetter [] = 0
singleLetter (l:ls) = numberFor [l] + singleLetter ls
where
numberFor l = snd $ findOrFail (finder l) atoms
finder l = (\x -> fst x == l)
intToRomanString :: Int -> String
intToRomanString 0 = ""
intToRomanString a = case (x) of
Just (letter,number) -> letter ++ intToRomanString (a - number)
Nothing -> error "romans did not have negative numbers"
where x = head' [(l,num) | (l,num) <- atoms, a - num >= 0]
romanToString :: Roman -> String
romanToString x = case (x) of
R x -> x
RN x -> intToRomanString x
romanToInt :: Roman -> Int
romanToInt x = case (x) of
RN x -> x
R x -> romanStringToInt x
head' [] = Nothing
head' (x:xs) = Just x
findOrFail x y = wrap $ find x y
where wrap x = case (x) of
Just that -> that
Nothing -> error "Could not find any element that satisfies condition"
view raw roman.hs hosted with ❤ by GitHub

Disclaimer: I may have only implemented a subset of the proper rules of how to write Roman numbers. If you use this type to calculate the altitude of your plane, and it doesn't work, don't sue me, because I give no guarantees as to the 100% correctness of the code

The Roman number cough system cough had no extraordinary mathematical capabilities - I am not aware of any systematic approach that would let you add two Roman numbers. Their only purpose must have been to attach a word to a number.

The interesting parts with regard to the type system are lines 8-22. What is defined here is

  • What a Roman is : It has two constructors that take a String or an Int
  • That a Roman can be shown, which makes it interesting e.g. in the interactive mode of Haskell
  • That two Romans can be compared
  • That a Roman behaves like a Num type

The rest is really just a fair enough implementation of how to get from something like MCMLXXXIV to 1984.

The (probably quite inaccurate) conclusions I take away from this quick splash into Haskell-land

  • Haskell classes can be compared somewhat to interfaces, but they can carry default implementations
  • Haskell data can have what could be compared to multiple constructors, but later on we can actually match on how data was constructed
  • Not used here, but Haskell has a decent record syntax (yes, I am pointing at you, Erlang)
  • The capabilities, or traits, or contracts or whatever you like to call them are much cleaner defined. Not every thing is by default equatable. Not every thing is by default displayable.

All in all, once again, refreshing, and purifying ;)

A knee-shot involving StructureMap, a closure and a leaking implementation detailAtrocious Learnings of Haskell for Make Benefit of solving Math Problem