Description
For this exercise you are expected to develop all of the programs below. The tutorials will work through the starred questions. You are expected to hand in (to gradescope) a documented Haskell script containing your solutions (including the programs discussed in the labs) … I encourage you to discuss these programs with your classmates: the aim is to complete these exercises (somehow –maybe not all the challenge questions!!) so that you get used to thinking in Haskell syntax and us-ing high-order functions. You should comment your code indicating, in particular, how you arrived at a solution. Recall that it is important that you understand the solutions as this comprehension will be tested in the tutorial written tests.
Recall, you are required to document the source of your code. You should not expect credit for code which you do not understand or to which you have not contributed. In particular, while it may help to use the functions from the Haskell’s prelude (or libraries) – especially to get you going – in the end you have to fully understand the code you submit … so in the end, to avoid losing marks (particularly for these beginning exercises) it is better to avoid prelude and library functions and to develop your own code.
The question with a star are likely to be discussed further in the labs …
Please name your functions according to what is prescribed below. Use the template provided for the exercise from my website.
1. A logical formula in two variable is a function of the form f :: (Bool; Bool) > Bool. Write a function
twoTautology:: ((Bool,Bool) -> Bool) -> Bool
which determines whether a logical formula f is always true (i.e. a tautology): to be a tautology it must be true for all possible arguments of f)! Now write a function which determines whether two logical functions of two variables are equivalent:
twoEquiv::((Bool,Bool)->Bool)->((Bool,Bool)->Bool)->Bool
This should be true when the functions agree on all inputs.
2. Write a function badFermat :: Integer
1
that shows Fermat’s conjecture (all numbers of the form 22n +1 are prime) is false by finding a number for which it is not true. What happens if the conjecture is true?
3. The function
collatz :: Int -> Int
is defined by collatz(n) = n=2 if n is even and collatz(n) = 3n + 1 if n is odd. It is believed that if collatz is applied repeatedly, then eventually one will see the num-ber 1. For example, collatz(5) = 16, and collatz(16) = 8, and collatz(8)
• 4, and collatz(4) = 2, and collatz(2) = 1. The Collatz index of a number (n 0) is the minimum number of times that collatz needs to be applied to obtain 1. For example, the Collatz index of 5 is 5, and the Collatz index of 7 is 16 (the sequence is [7; 22; 11; 34; 17; 52; 26; 13; 40; 20; 10; 5; 16; 8; 4; 2; 1]. Write a Haskell function
collatzIndex :: Int -> SF [Int]
which computes the Collatz “index” of a number by calculating the sequence ending in 1. What happens if a number has no Collatz index?
4. The bisection method is a neat way to find (approximate) roots to continuous functions – it has advantages to Newton’s method because it only requires the function to be continu-ous instead of differentiable. Fix e to be a really small number (sometimes called machine epsilon) by making it a constant
e :: Double
e = 2ˆˆ(-6)
We will regard any x with jxj < e as being effectively zero. Let f : R ! R be a continuous function, and a and b are numbers for which f(a) and f(b) have opposite signs. Then f has a zero (crosses the axis) in the interval [a; b]. The bisection method computes the midpoint, m, of a and b, and then compares the sign of f(a), f(b), f(m). One of the pairs (f(a); f(m)) or (f(m); f(b)) have opposite signed numbers, or m is a root jf(m)j < e. Use this information to either return the root, or continue searching on a smaller interval. Write a Haskell program
bisection::(Double->Double)->(Double,Double)-> SF Double
which given a function f and a pair of initial values (a; b), returns, when f(a) and f(b) are of opposite sign or one is effectively zero, the value (up to e!) of a zero crossing for the function f.
5. Implement bubble sort, quicksort, and merge sort in Haskell:
bsort::(Ord a) => [a] -> [a]
qsort::(Ord a) => [a] -> [a]
msort::(Ord a) => [a] -> [a]
2
6. A matrix in Haskell can be represented by the type
type Matrix a = [[a]]
type DoubleMatrix = Matrix Double
Write functions
dimension:: Matrix a -> SF (Int,Int) — (outer,inner)
transpose:: Matrix a -> (SF (Matrix a))
addMat :: DoubleMatrix -> DoubleMatrix -> (SF DoubleMatrix)
multMat :: DoubleMatrix -> DoubleMatrix -> (SF DoubleMatrix)
Which returns a matrix (or its dimensions) when these functions are well-defined.
7. Implement list reversal in three different ways: naive reverse, fast reverse, a higher-order reverse (using a fold right):
nreverse:: [a] -> [a]
freverse:: [a] -> [a]
hreverse:: [a] -> [a]
8. Given an expression tree
data Expr f x = Fun f [Expr f x]
| Var x
determine the list of all paths to leaves determined by pairs, ([f],x), of node values from root to leaf and the leaf value, with paths enumerated from left to right:
all_paths:: Expr f x -> [([f],x)]
9. (For fun:) Calculate the factorial of 1,891 or explain six different ways of programming fac-torial (see http://www.willamette.edu/ fruehr/haskell/evolution.html).
10. (This is a challenging question!) Given a Rose tree data Rose a = RS a [Rose a]
calculate the width of the tree (that is, in the undirected graph of the tree, the length of the longest path):
widthRose:: Rose a -> Int Hint, can you do this using a fold?
3
11. An AVL tree is a binary search tree:
data STree a = Node (STree a) a (STree a)
| Leaf
consisting of a tree of items which are ordered satisfying two conditions
(a) The value of an item at a node is larger than any item in its left tree and smaller than any item in its right tree
(b) The tree is balanced: the difference in height between the left tree and right tree at any node is at most 1.
Write functions to determine whether a tree is ordered (so satisfies (a)) or is balanced (so satisfies (b)):
is_ordered:: (Ord a) => STree a -> Bool
is_balanced:: STree a -> Bool
(Why does testing whether a tree is balanced not require Ord a?)
Finally (much harder for those who wish to be challenged) can you write a function which given an ordered tree strongly balances it (in the sense of each node having the difference in size between left and right nodes no greater than one) by performing a minimal number of rotations:
strong_balance:: STree a -> STree a
4
