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.
a) Declare a polymorphic type class Dictionary
k v 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.
The lambda calculus is a theoretical
programming language that contains only variables, function
applications, and lambdas. For example, the lambda calculus term λx.
λy. λf. f (x y) is equivalent to the Haskell expression \x ->
\y -> \f -> f (x y).
In the lambda calculus we may represent natural numbers using Church numerals, as follows:
0 = λf.λx.x
1 = λf.λx.f x
2 = λf.λx.f (f x)
3 = λf.λx.f (f (f x))
...
a) What are the polymorphic types of the Church numerals 0, 1, and 2? Is there some polymorphic type τ such that all Church numerals belong to the type τ?
b) Write a Haskell function that converts a Church
numeral to an Integer.
c) Write a Haskell function that converts an
Integer to a Church numeral.
d) Write a function that adds two Church numerals. (Do not use Haskell integers in your solution.)
e) Write a function that multiplies two Church numerals. (Do not use Haskell integers in your solution.)
As you may have learned in an automata class, a finite state machine consists of
a finite set of states
a finite set of input symbols
a transition function that maps a state and an input symbol to a new state
a start state
a set of final (or accepting) states
In this exercise we will consider finite state machines whose states are integers and whose input symbols are characters.
a) Design finite state machines that accept the following sets of characters, represented by regular expressions:
ab(..)*
(.*)aaba(.*)
b) Design a representation for finite state machines in Haskell.
c) Write a function accept that takes
a finite state machine and a string, and returns true if the the
machine accepts the string. Use your function to test the finite
state machines that you defined in part (a).
Solve Project Euler #39 "Integer Right Triangles".
Solve Project Euler #40 "Champernowne's Constant". Use an infinite list.