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. 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. Your type should belong to the Eq, Ord, and Show type classes.

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

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

4. Lists

Pretend that Haskell does not have a built-in list type.

a) Implement lists using a data type List a. Comparison operators (e.g. ==, /=, >, <) should work on your class and should compare lists lexicographically.

b) Declare that List is an instance of the type class Functor.

c) Write a function that performs a right fold over a List of any type. It should have this type:

    foldr :: (b → a → a) → a → List b → a

5. Dictionary

a) Declare a type class Dictionary that represents a mapping from element of type 'k' to type 'v'. It should have an empty dictionary value, plus operations to get or set the value for a given key. Retrieving the value of an absent key should return Nothing. Assume that keys are orderable.

b) Declare a datatype Assoc k v representing an association list, i.e. a list of key-value pairs. Declare that Assoc is an instance of Dictionary. Also declare that it is an instance of Functor. fmap should affect the values (not the keys) stored in the association list.

c) Declare a binary tree type that can map keys to values. Declare that it is an instance of Dictionary. Also declare that it is an instance of Functor. fmap should affect the values (not the keys) stored in the tree.

6. Fibonacci List

In last week's lecture we saw a function that can generate a list of all Fibonacci numbers:

fibsFrom :: Integer -> Integer -> [Integer]
fibsFrom i j = i : fibsFrom j (i + j)

Generate this list using a recursive value definition.

7. N Queens

Is it possible to place N queens on an N x N chessboard such that no two queens attack each other?

a) Write a function that can produce a list of all possible solutions for a given N, where each solution is a list of positions of queens on the board. Use an exhaustive search. For example:

> queens 4
[[(2,1),(4,2),(1,3),(3,4)],[(3,1),(1,2),(4,3),(2,4)]]

b) Modify your function to return a list of strings, where each string depicts a possible solution:

> queens 4
[". Q . . \n. . . Q \nQ . . . \n. . Q . \n",". . Q . \nQ . . . \n. . . Q \n. Q . . \n"]

To see the output nicely in the REPL, you can use I/O functions (which we haven't learned about yet):

> mapM_ putStrLn (queens 4)
. Q . . 
. . . Q 
Q . . . 
. . Q . 

. . Q . 
Q . . . 
. . . Q 
. Q . .

8. Linear Congruential Generator

A linear congruential generator is a formula for generating a series of pseudorandom numbers. It has the form

Xn+1 = (a Xn + c) mod m

where X is the series of pseudorandom values, and a, c, and m are constants.

Use a linear congruential generator to construct an infinite list of values of type Double in the range from 0.0 to 1.0. Use the constants