Week 10: Exercises

1. Time

a) Create a Haskell type Time that represents a time of day with 1-second resolution, such as 5:15:02 or 13:12:45. Create a function time :: Int -> Int -> Int -> Time that constructs a Time from values h, m, and s, where 0 <= h < 24 and 0 <= m, s < 60.

b) Declare that Time is an instance of the type classes Eq, Ord, Enum, Bounded, and Show.

c) Write a function add :: Time -> Int -> Time that adds a (positive or negative) number of seconds to a Time, wrapping past midnight if necessary.

2. Fractions

Consider the GFrac datatype that we saw in the lecture, representing a fraction:

data GFrac t = GFrac t t

instance (Eq t, Num t) => Eq (GFrac t) where
    (==) (GFrac a b) (GFrac c d) = (a * d == b * c)

Declare that this datatype is an instance of the Ord and Num type classes.

3. Arrays

a) Write a function toArray :: [a] -> Array Int a that converts a list to an array with integer indices, indexed from 0.

b) Write a function array2d :: [[a]] -> Array (Int, Int) a that converts a list of lists to a 2-dimensional array with integer indices, indexed from 0.

4. Minimum Number of Coins

a) Write a function coins :: [Int] -> Int -> Int that takes a list of coin denominations and a sum, and returns the mininum number of coins required to form the sum. Any denomination may be used multiple times in forming the sum. For example, coins [1, 2, 5, 10] 9 will return 3, because 2 + 2 + 5 = 9.

b) Modify your function so that it has type [Int] -> Int -> [Int], and will return a minimal list of coins which can be used to form the sum. For example, coins [1, 2, 5, 10] 9 might return the list [2, 2, 5].

5. Integer Partition

Write a function partition :: [Int] -> Maybe ([Int], [Int]) that takes a list of integers and determines whether it can be partitioned into two sets whose sum is equal. If so, the function should return a Just with two lists containing the numbers in each set. If not, it should return Nothing.

6. Natural Numbers

Pretend that Haskell does not have the built-in types Int and Integer.

a) Implement natural numbers (i.e. non-negative integers) using a data type Nat. Comparison operators (e.g. ==, /=, >, <) should work correctly on your class.

b) Implement an addition function add :: Nat -> Nat -> Nat.

c) Implement a multiplication function mul :: Nat -> Nat -> Nat.

7. Infinite Diagonal Matrix

Construct an infinite diagonal matrix as an infinite list of lists:

[[1, 0, 0, 0, ...],
 [0, 1, 0, 0, ...],
 [0, 0, 1, 0, ...],
 .
 .
 .
 ]