FORMATIVE 3
Remarks
– Copy the file Formative3-Template.hs to a new file called Formative3.hs and write your solutions in Formative3.hs. Don’t change the header of this file, _including the module declaration_, and, moreover, _don’t_ change the type signature of any of the given functions for you to complete.
– Solve the exercises below in the file Formative3.hs.
– In this assignment you are allowed to use Haskell library functions that are available in CoCalc. Look it up at Hoogle.
– Run the pre-submit script to check for any (compilation) errors BEFORE submitting by running in the terminal:
$ ./presubmit.sh Formative3
– Submit your file Formative3.hs via Canvas at https://canvas.bham.ac.uk/courses/46061/assignments/252201 .
Exercises
Q1: Folding an expression
Consider the type declaration
data Expr = Val Int | Add Expr Expr
Exercise 1.
Define a higher-order function
folde :: (Int -> a) -> (a -> a -> a) -> Expr -> a
such that folde f g replaces each Val constructor in an expression by the function f, and each Add constructor by the function g.
(We’ll consider some examples of using folde below.)
Q2: Using folding
Exercise 2a.
Using folde, define a function
eval :: Expr -> Int
that evaluates an expression to an integer value.
For example,
eval (Add (Val 1) (Add (Val 2) (Val 3))) = 6
Exercise 2b.
Using folde again, define a function
size :: Expr -> Int
that calculates the number of values in an expression.
For example,
size (Add (Val 1) (Add (Val 2) (Val 3))) = 3
Q3: Fold to a string
Exercise 3.
Using folde, define a function
exprToString :: Expr -> String
that converts an expression to a string.
For example,
exprToString (Add (Val 1) (Add (Val 2) (Val 3))) = “1 + 2 + 3”
Q4: Defining type class instances
Consider the following datatypes
data MyMaybe a = MyNothing | MyJust a
data MyList a = MyEmpty | MyCons a (MyList a)
Complete the following instance declarations: ##### Exercise 4a.
instance Eq a => Eq (MyMaybe a) where
Exercise 4b.
instance Eq a => Eq (MyList a) where
Exercise 4c.
instance Ord a => Ord (MyMaybe a) where
Q5: Text messaging
(From “Haskell Programming”)
Remember old-fashioned phone inputs for writing text, where you had to press a button multiple times to get different letters to come up? You may still have to do this when you try to search for a movie to watch using your television remote control. You’re going to write code to translate sequences of button presses into strings and vice versa. Here is the layout of the phone:
—————————————–
| 1 | 2 ABC | 3 DEF |
—————————————–
| 4 GHI | 5 JKL | 6 MNO |
—————————————–
| 7 PQRS | 8 TUV | 9 WXYZ |
—————————————–
| * | 0 | # ., |
—————————————–
The star (*) capitalizes the current letter (if you press it twice, then it reverts to lower case), and 0 is your space bar. To represent the digit itself, you press that digit once more than the letters it represents. If you press a button one more than is required to type the digit, it wraps around to the first letter. For example:
2 -> ‘a’
22 -> ‘b’
222 -> ‘c’
2222 -> ‘2’
22222 -> ‘a’
0 -> ‘ ‘
00 -> ‘0’
000 -> ‘ ‘
1 -> ‘1’
11 -> ‘1’
111 -> ‘1’
You will not need to type ‘#’, so
# -> ‘.’
## -> ‘,’
### -> ‘.’
Consider the following datatypes:
— Valid buttons are [‘0’..’9′]++[‘*’,’#’]
type Button = Char
— Valid presses are [1..]
type Presses = Int
— Valid text consists of
— [‘A’..’Z’]++[‘a’…’z’]++[‘0’..’9′]++[‘.’,’,’,’ ‘]
type Text = String
Exercise 5a.
Write a function
phoneToString :: [(Button, Presses)] -> Text
that takes a list of buttons and the number of times to press them and gives back the corresponding text, e.g.
phoneToString [(‘*’,1),(‘6’,5),(‘5’,4)] = “M5”
Exercise 5b.
Write a function
stringToPhone :: Text -> [(Button, Presses)]
taking a string to a list of buttons and the number of times that they need to be pressed, e.g.
stringToPhone “Hi, students.” = [(‘*’,1),(‘4’,2),(‘4’,3),(‘#’,2),(‘0’,1),(‘7’,4),(‘8’,1),(‘8’,2),(‘3’,1),(‘3’,2),(‘6’,2),(‘8’,1),(‘7’,4),(‘#’,1)]
Exercise 5c.
Write a function
fingerTaps :: Text -> Presses
that computes the minimal number of button presses needed to input the given string, e.g.
fingerTaps “Hi, students.” = 27
Q6: Quick sort in monadic form
The following is the standard quick sort algorithm:
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (p:xs) = qsort [x | x <- xs, x < p]
++ [p]
++ qsort [x | x <- xs, x >= p]
Exercise 6.
Write it in monadic form by completing the following definition:
qsortm :: (Ord a , Monad m) => [a] -> m [a]
HINT. See how we converted the Fibonacci function to monadic form in the handout on monads.
Q7: Random quick sort
The head element p in above definition of qsort is called the pivot. Choosing the pivot as the head element, or any other fixed element, of the list causes efficiency problems. The _average_ run time of the above quicksort is $`n \log n`$ where $`n`$ os the length of the input list, which is good. However, the _worst case_ run time is $`n^2`$, which is not as good. In particular, choosing the head as the pivot always gives rise to run time $`n^2`$ for sorted lists and for nearly sorted lists, which occur often in practice.
One way to guarantee the better run time of $`n \log n`$ with high probability is to choose the pivot randomly among the elements of the list. This algorithm is called randomized quick sort. In this question we create a monad for randomness for this and other purposes. You objective is to implement randomized quick sort.
The following definition needs import System.Random, which defines a type StdGen of random generators. You can think of the given random generator as a seed.
data Rand a = Generator (StdGen -> (a , StdGen))
The idea is that a function of type StdGen -> (a , StdGen) describes a process that given a random generator produces an element of the type a and a new random generator, in a pair.
We define the monad as follows:
instance Monad Rand where
return x = Generator (\g -> (x,g))
Generator h >>= f = Generator (\g -> let (x, g’) = h g
(Generator h’) = f x
in h’ g’)
Usually we first define Functor and Applicative and then Monad, but it is possible to do this the other way round. We define the Functor and Applicative from the monad here:
instance Functor Rand where
fmap f xm = xm >>= return . f
instance Applicative Rand where
pure = return
fm <*> xm = fm >>= \f -> xm >>= return . f
Like for the State and Writer monads, we have a function runRand to extract a value from the type Rand a. This function needs a seed:
runRand :: Int -> Rand a -> a
runRand seed (Generator h) = fst (h (mkStdGen seed))
The following function computes a random number. It uses the function random from System.Rand, which has precisely the type we need:
randInt :: Rand Int
randInt = Generator random
The following is similar, but instead uses randomR to get an integer in a range:
randIntR :: (Int, Int) -> Rand Int
randIntR (lower, upper) = Generator (randomR (lower, upper))
Here is an example of a use of the monad. The following function randomly picks an element of a non-empty list with “uniform distribution”, which means that all elements are equally likely:
uniform :: [a] -> Rand a
uniform [] = undefined
uniform xs = do
n <- randIntR (0, length xs - 1)
return(xs !! n)
We can finally implement randomized quick sort. We write a helper function for you to use if you wish:
getPivot :: [a] -> Int -> (a, [a])
getPivot (x:xs) 0 = (x,xs)
getPivot (x:xs) n = let (p,ys) = getPivot xs (n-1) in (p, x:ys)
Exercise 7a.
Write a monadic randomized quick sort, by randomly picking the pivot at each recursive call:
rqsort :: Ord a => [a] -> Rand [a]
We can get rid of the monad using runRand:
rqsort’ :: Ord a => [a] -> [a]
rqsort’ xs = runRand seed (rqsort xs)
where seed = 42 — say
Exercise 7b.
Test this on large lists, including sorted lists, and compare the run time with that of qsort, using the ghci command :set +s.
(You don’t need to submit your tests.)