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.
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.
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.
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
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.
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 . .
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
a = 1,664,525
c = 1,013,904,223
m = 232
Solve Project Euler #39 "Integer Right Triangles".