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
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.
Write a function compositions :: Int ->
[[Int]] that takes a natural number N and returns a list of
all sets of positive integers that add up to N. Order matters: 1 + 2
and 2 + 1 are distinct compositions of N = 3.
A partition of a positive integer n is a set of positive integers that add up to n. For example, the number 4 has 5 partitions:
1 + 1 + 1 + 1 2 + 1 + 1 2 + 2 3 + 1 4
Write a function partitions :: Int -> [[Int]] that
produces a list of all partitions of a positive integer.
Write a function coins :: [Int] -> Int ->
[[Int]] that takes a list of coin denominations and a sum, and
returns a list of all ways to form the sum using coins from the set.
Any coin may be used multiple times in forming the sum. Order does
not matter: for example: the function should not return both [1,
1, 2] and [2, 1, 1].
Write a function min_coins :: [Int] ->
Int -> Just [Int] that takes a list of coin denominations
and a sum, and returns a minimal list of coins which can be used to
form the sum. Any coin may be used multiple times in forming the sum.
For example, coins [1, 2, 5, 10] 9 might return the list
[2, 2, 5]. If it is not possible to form the given sum
from the given coins, return Nothing.
Write
a function eq_partition
:: [Int] -> Maybe ([Int], [Int]) that
takes a list of integers and determines whether it can be partitioned
into two sets whose sums are equal. If so, the function should return
a Just
with
two lists containing the numbers in each set. If not, it should
return Nothing.
Write a function that can insert a value into a binary search tree. Choose an appropriate type for your function.
Using the function you wrote in part (a), write a function that inserts all values in a given list into a binary search tree.
We will say that a binary tree is balanced if for every node in the tree, the left and right subtrees differ in height by at most 1. Write a function that takes a binary tree and returns True iff it is balanced.
We can use this an algebraic data type to represent an arithmetic expression:
data Expr = Const Int | Var String |
Add Expr Expr | Sub Expr Expr | Mul Expr Expr
a) Write a function parse :: String -> Expr that can
parse an expression written in prefix notation, such as
* + x y - x y * z - z 2 14 + 0 + 1 + 2 3
You may assume that (as in the examples above) all input tokens are separated by spaces.
b) Write a function eval :: [(String, Int)]
-> Expr -> Int that evaluates an expression. The first
argument to the function is an environment, i.e. an
association list that maps variables to their values.
Write a function simplify :: Expr -> Expr
that simplifies an expression by combining constants wherever
possible, and by eliminating additions/subtractions with 0 or
multiplications with 1.
For example, 0 + (x + (2 + 3)) should simplify to x + 5.
Write
a function break
::
[String]
->
String
->
Maybe
[String]
that
takes two arguments: a dictionary of words plus a string. If it is
possible to break the string into some sequence of words from the
dictionary, the function should return a list of those words,
otherwise Nothing. For example, break
["black",
"blue",
"green",
"red",
"white"]
"redgreenblue"
should
return Just
["red",
"green",
"blue"].
If
there is more than one possible way to break the string into words,
the function may return any of these.
Write a function triples that takes
an integer N and returns a list of integer triples (a, b, c) with
0 < a < b < c ≤ N such that
a2 + b2 = c2. If two triples are
multiples of each other (e.g. (3, 4, 5) and (6, 8, 10)),
only the smaller of them (e.g. (3, 4, 5)) should appear in the list.
> triples 15 [(3,4,5),(5,12,13)]
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).
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 . .
Solve Project Euler #39 "Integer Right Triangles".
Solve Project Euler #40 "Champernowne's Constant". Use an infinite list.