Martin Sulzmann
This exercise is about (simple) data types and list processing where as an example we consider the representation and processing of digits.
Some runnable code template provided here.
data Digit = Zero | One | Two | Three | Four | Five | Six | Seven | Eight | Nine deriving (Eq, Ord)
instance Show Digit where
show Zero = "0"
show One = "1"
show Two = "2"
show Three = "3"
show Four = "4"
show Five = "5"
show Six = "6"
show Seven = "7"
show Eight = "8"
show Nine = "9"
newtype Digits = Digits [Digit] deriving Eq
instance Show Digits where
show (Digits xs) = concat $ map show xs
Points to note:
deriving
newtype
Via deriving
we let the compiler automatically generate
some standard instances.
Instead of the newtype
declaration we could have also
used data
. However, there is only case (there are no
alternatives). For this special case, newtype
is
more efficient (from the compiler’s perspective).
We provide a simple parser for digits. The parse function shall be
applied on a single digit as well as on a sequence of digits. Hence, we
introduce a Parse
type class with some overloaded method
parse
.
class Parse a where
parse :: String -> a
instance Parse Digit where
parse "0" = Zero
parse "1" = One
parse "2" = Two
parse "3" = Three
parse "4" = Four
parse "5" = Five
parse "6" = Six
parse "7" = Seven
parse "8" = Eight
parse "9" = Nine
instance Parse Digits where
parse xs = Digits $ map (\x -> parse [x]) xs
Here’s a simple test function to play around with digits.
test1 = do
putStrLn "Key in sequences of digits"
s <- getLine
let ds = parse s :: Digits
putStrLn $ "Keyed in digits are: " ++ show ds
You’ll need to call test1
as part of
main
.
The type annotation parse s :: Digits
is necessary
because parse
is overloaded based on the return type. As we
later call show
the compiler would not be able to figure
out the to be parsed type.
Our current parser yields a run-time error if we key in some non-digits. The parser below is more robust and exits gracefully if we encounter some non-digits.
instance Parse (Maybe Digit) where
parse [x]
| elem x ['0'..'9'] = Just $ parse [x]
| otherwise = Nothing
parse _ = Nothing
instance Parse (Maybe Digits) where
parse xs
| any (\x -> not (elem x ['0'..'9'])) xs = Nothing
| otherwise = Just $ parse xs
test2 = do
putStrLn "Key in sequences of digits"
s <- getLine
let r = parse s :: Maybe Digits
case r of
Nothing -> putStrLn "Invalid sequence"
Just ds -> putStrLn $ "Keyed in digits are: " ++ show ds
Here’s a simple implementation of a function that computes the cross sum of a sequence of digits.
crossSum :: Digits -> Int
crossSum (Digits ds) = sum $ map (\d -> read (show d) :: Int) ds
test3 = do
putStrLn "Key in sequences of digits"
s <- getLine
let r = parse s :: Maybe Digits
case r of
Nothing -> putStrLn "Invalid sequence"
Just ds -> do putStrLn $ "Keyed in digits are: " ++ show ds
putStrLn $ "Cross sum = " ++ show (crossSum ds)
The read
function converts a string into the provided
type (and might fail if a conversion is not possible).
Implement the following function.
numOfOcc d ds
yields the number of occurrences of
d
in ds
.
Here are some examples.
numOfOcc Zero (Digits [Nine,Five]) ===> 0
numOfOcc Zero (Digits [Nine,Five,Zero,Three,Zero]) ===> 2
Implement the following function.
Yields the digit that occurs most frequently (including the number of occurrences). There can be several “most frequent” digits. Here are some examples.
mostFrequentDigit (Digits [Nine,Five,Zero,Three,Zero]) ===> [(Zero,2)]
mostFrequentDigit (Digits [Nine,Five,Zero,Three,Zero,Three]) ===> [(Zero,2),(Three,2)]
The sequence of digits shall be interpreted as a number. Implement the following type class instance to guarantee that digits are ordered based on the number they represent.
Improve the parser for sequences of digits as follows.
Blanks shall be ignored
Check if a prefix of some input can be parsed.
For example, inputs such as “3 5xyz” yield an error but we wish to
obtain the sequence of digits Three
and
Five
.