Haskell exercise (“digits”)

Martin Sulzmann

Overview

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.

Digits

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:

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).

Simple parser

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.

More robust parser

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

Cross sum

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).

Task: Number of occurrences

Implement the following function.

numOfOcc :: Digit -> Digits -> Int

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

Task: Most frequent digit

Implement the following function.

mostFrequentDigit :: Digits -> [(Digit,Int)]

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)]

Task: Ordering among sequence of digits

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.

instance Ord Digits where

Task: Even more robust parser

Improve the parser for sequences of digits as follows.

For example, inputs such as “3 5xyz” yield an error but we wish to obtain the sequence of digits Three and Five.