# Assessed Assignment 1
## Marking table
The exercises are defined so that it is hard to get a first-class mark.
“`
1st class – 70 marks and above.
upper snd – 60-69 marks.
lower snd – 50-59 marks.
third class – 40-49 marks.
fail – 0-39 marks.
“`
All questions have equal weight.
## Preparation
* Do __not__ modify the files `Types.hs` and `Assessed1-Template.hs`.
* Copy the file `Assessed1-Template.hs` to a new file called `Assessed1.hs` and write your solutions in `Assessed1.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.__
__If you do make changes, then we will not be able to mark your submission and hence it will receive zero marks!__
* Solve the exercises below in the file `Assessed1.hs`.
## Submissions should compile and run correctly on Jupyter Notebook
If your submission doesn’t compile or run correctly on Jupyter Notebook, it will get zero marks.
## Submission procedure
* Run the presubmit script to be provided to you on your submission from Jupyter by running `./presubmit.sh Assessed1` in the terminal (in the same folder as your submission).
* This will check that your submission is in the correct format.
* If it is, submit on Canvas.
* Otherwise fix and repeat the presubmission procedure.
## Plagiarism
Plagiarism will not be tolerated. Copying and contract cheating has led to full loss of marks, and even module or degree failure, in the past.
You will need to sign a declaration on Canvas, before submission, that you understand the [rules](/plagiarism) and are abiding by them, in order for your submission to qualify.
## Background material
– Each question has some **Background Material**, an **Implementation Task** and some **Examples**.
– Read this material first, then implement the requested function.
– The corresponding type appears in the file `Assessed1Template.hs` (to be copied by you).
– Replace the default function implementation of `undefined` with your own function.
## Exercise 1 – Checksum
### Background Material
A *checksum* is an extra collection of bits added to some data in
order to force it to satisfy a certain property. This property can
then be used to quickly detect simple errors which may happen during
communication. For example, when choosing student ID numbers, we can
first choose an initial set of digits any way we please, and then add
digits to the end of the number in order to force the sum of the
digits to be divisible by 11. By then verifying that this condition
holds whenever we process data containing the ID, we equip ourselves
with a basic sanity check.
### Implementation Task
Write a function
“`haskell
checksum :: Integral a => [a] -> Bool
checksum = undefined
“`
that takes as input a list of numbers and checks that
1. The list is 8 elements long
2. The sum of the numbers is divisible by 11.
The function should return `True` if both of these conditions are met, and `False` otherwise.
### Examples
“`hs
*Main> checksum [8,3,2,3,8,7,0,2]
True
*Main> checksum [8,3,2,3,8,9,1,2]
False
*Main> checksum [4,5,8,2,4]
False
“`
## Exercise 2 – Rainbow
### Background Material
We are going to change the Game of Life to include colours. The colour
of a new cell (a “child”) will be a blend of the colours of its alive
neighbours (its “parents”).
Consider the following configuration where the dead cell in the lower
left is to come alive, since it is surrounded by three neighbours:
We will compute the color of the new child by averaging the red, green
and blue values of its parents. In this example, this average makes
the child grey:
To implement this idea, we begin by defining a type of colors. A
colour is a RGB (Red, Green, Blue) triple with values 0 – 255.
“`hs
type Colour = (Int, Int, Int)
red, green, blue, yellow :: Colour
red = (255, 0, 0)
green = (0, 255, 0)
blue = (0, 0, 255)
yellow = (250, 163, 7)
red1, red2 :: Colour
red1 = (106, 4, 15)
red2 = (208, 0, 0)
“`
We will need to take the average of a list of numbers, and we can do
this using the funcion `avg`, defined as follows:
“`hs
avg :: [Int] -> Int
avg ns = sum ns `div` length ns
“`
Next, we can define our `blend` function by computing the averages of the RGB
components of a list of colours:
“`hs
blend :: [Colour] -> Colour
blend cs = (avg rs , avg gs , avg bs)
where
rs = [r | (r,g,b) <- cs]
gs = [g | (r,g,b) <- cs]
bs = [b | (r,g,b) <- cs]
```
We will need to redefine cells to carry not only their coordinate, but
also a colour. This can be done as follows:
```hs
type Coordinate = (Int, Int)
type Cell = (Coordinate, Colour)
```
Using the standard functions `fromJust` and `lookup` (which will be explained in
later lectures) we can easily get the colour of a cell (specified by a coordinate)
in a grid.
```hs
colourOf :: Grid -> Coordinate -> Colour
colourOf g coord = fromJust (lookup coord g)
“`
To see an example, let’s add colours to the `glider` grid like this:
“`hs
glider :: Grid
glider = [((1,3), red1),((2,1), yellow),((2,3), red2),((3,2), red2),((3,3), yellow)]
“`
Rendering the grid gives the following output:
Stepping it once then gives:
And another step leads to:
We will also need to display our colors on the screen. Recall that in
the original Game of Life we saw that we can use escape codes to clear
the terminal or move the cursor. We can also use escape codes to print
colours as follows:
“`hs
code :: Colour -> String
code (r, g, b) = show r ++ “;” ++ show g ++ “;” ++ show b ++ “m”
escapeStart :: String
escapeStart = “\ESC[38;2;”
escapeStop :: String
escapeStop = “\ESC[0m”
— Print a coloured string.
colourStr :: Colour -> String -> String
colourStr c s = escapeStart ++ code c ++ s ++ escapeStop
“`
With these functions in hand, the only change we need to make in
printing the cells to replace `putChar ‘0’` by `putStr (colourStr c
“0”)` (where `c` is colour) in the `printCell` function. This gives
us:
“`hs
printCell :: Cell -> IO ()
printCell ((x, y), c)
| x >= 0 && x < terminalWidth
&& y >= 0 && y < terminalHeight = do
goto (x,y)
putStr (colourStr c "O")
| otherwise = return ()
```
### Implementation Task
Your task is to rewrite the function
```haskell
step :: Grid -> Grid
step = undefined
“`
to take into account these changes. Specifically, this function returns a new grid such that the colour of any new cell (a “child”) will be the blend of the colours of its alive neighbours (its “parents”).
__NB: You can find the old `step` here [in this paragraph](/LectureNotes/Sections/Life.md#representing-the-board-and-step-function) in the lecture notes.__
### Examples
The `glider` example from above looks as follows:
“`hs
*Main> glider
[((1,3),(106,4,15)),((2,1),(250,163,7)),((2,3),(208,0,0)),((3,2),(208,0,0)),((3,3),(250,163,7))]
*Main> step glider
[((1,2),(188,55,7)),((2,4),(188,55,7)),((2,3),(208,0,0)),((3,2),(208,0,0)),((3,3),(250,163,7))]
*Main> step (step glider)
[((1,3),(194,36,4)),((3,4),(215,72,4)),((2,4),(188,55,7)),((3,2),(208,0,0)),((3,3),(250,163,7))]
“`
Remember that **the order of cells** within the grid **does not matter**. Your step function output may differ, but as long as the exact same cells are present, the grid is still valid.
Let’s look at a more complicated example. The “glider gun” can be defined by the following grid:
“`hs
glider_gun :: Grid
glider_gun = [((13,1),(0,0,255)),((14,1),(0,0,255)),((12,2),(0,0,255)),((16,2),(0,0,255)),((11,3),(0,0,255)),((17,3),(0,0,255)),((25,3),(255,0,0)),((1,4),(0,0,255)),((2,4),(0,0,255)),((11,4),(0,0,255)),((15,4),(0,0,255)),((17,4),(0,0,255)),((18,4),(0,0,255)),((23,4),(255,0,0)),((25,4),(255,0,0)),((1,5),(0,0,255)),((2,5),(0,0,255)),((11,5),(0,0,255)),((17,5),(0,0,255)),((21,5),(255,0,0)),((22,5),(255,0,0)),((12,6),(0,0,255)),((16,6),(0,0,255)),((21,6),(255,0,0)),((22,6),(255,0,0)),((35,6),(255,0,0)),((36,6),(255,0,0)),((13,7),(0,0,255)),((14,7),(0,0,255)),((21,7),(255,0,0)),((22,7),(255,0,0)),((35,7),(255,0,0)),((36,7),(255,0,0)),((23,8),(255,0,0)),((25,8),(255,0,0)),((25,9),(255,0,0))]
“`
which looks like
Stepping it once gives
“`hs
*Main> step glider_gun
[((10,4),(0,0,255)),((12,3),(0,0,255)),((12,4),(0,0,255)),((12,5),(0,0,255)),((13,2),(0,0,255)),((13,6),(0,0,255)),((18,3),(0,0,255)),((18,5),(0,0,255)),((20,6),(255,0,0)),((22,4),(255,0,0)),((22,8),(255,0,0)),((23,5),(255,0,0)),((23,6),(255,0,0)),((23,7),(255,0,0)),((24,3),(255,0,0)),((24,4),(255,0,0)),((24,8),(255,0,0)),((24,9),(255,0,0)),((1,4),(0,0,255)),((1,5),(0,0,255)),((2,4),(0,0,255)),((2,5),(0,0,255)),((11,3),(0,0,255)),((11,4),(0,0,255)),((11,5),(0,0,255)),((12,2),(0,0,255)),((12,6),(0,0,255)),((13,1),(0,0,255)),((13,7),(0,0,255)),((17,3),(0,0,255)),((17,4),(0,0,255)),((17,5),(0,0,255)),((18,4),(0,0,255)),((21,5),(255,0,0)),((21,7),(255,0,0)),((35,6),(255,0,0)),((35,7),(255,0,0)),((36,6),(255,0,0)),((36,7),(255,0,0))]
“`
After running this for a couple of steps we get the following configuration:
notice how the formed glider is a blend of the colours of the two sides.
# Exercise 3 – Binary Logic
## Background Material
In the second lab, we defined a function `orB :: Bool -> Bool -> Bool` that takes two boolean arguments and produces `True` if at least one argument is `True`, and `False` otherwise. Instead of implementing these logic functions on the values `True` and `False` of type `Bool`, let’s instead implement them on binary digits using the type `Binary` defined as:
“`hs
data Binary = Zero | One
deriving (Eq, Show, Bounded, Enum)
“`
Of course the type `Binary` is equivalent to the type `Bool`. We can verify this by defining two functions `bin2Bool :: Binary -> Bool` and `bool2Bin :: Bool -> Binary` checking that:
1. Given any `x :: Bool`, `(bin2Bool . bool2Bin) x == x`,
2. Given any `b :: Binary`, `(bool2Bin . bin2Bool) b == b`.
Intuitively, this says that when we transform a binary digit to a
boolean and then back again, we end up with the original boolean.
(**Note**: In the above, the `(.)` operation composes two functions,
i.e. `(f . g) x` means `f (g x)`).
## Implementation Tasks
**(a)** Implement the two functions
“`haskell
bin2Bool :: Binary -> Bool
bin2Bool = undefined
bool2Bin :: Bool -> Binary
bool2Bin = undefined
“`
in such a way that they satisfy the equations described above. Note that there is more than one way to get a correct answer.
**(b)** Implement the three logical functions
“`haskell
notBin :: Binary -> Binary
notBin = undefined
andBin :: Binary -> Binary -> Binary
andBin = undefined
orBin :: Binary -> Binary -> Binary
orBin = undefined
“`
which correspond to the functions `not`, `&&` and `||` under the translation you wrote in part **(a)**. This means that your implementations should satisfy the following conditions:
1. Given any `x :: Bool`, `not x == bin2Bool (notBin (bool2Bin x))`,
2. Given any `x :: Bool` and `y :: Bool`, “(x && y) == bin2Bool ((bool2Bin x) `andBin` (bool2Bin y))“,
3. Given any `x :: Bool` and `y :: Bool`, “(x || y) == bin2Bool ((bool2Bin x) `orBin` (bool2Bin y))“.
**(c)** Implement four functions
“`haskell
deMorg1 :: Binary -> Binary -> Binary
deMorg1 = undefined
deMorg2 :: Binary -> Binary -> Binary
deMorg2 = undefined
deMorg3 :: Binary -> Binary -> Binary
deMorg3 = undefined
deMorg4 :: Binary -> Binary -> Binary
deMorg4 = undefined
“`
which correspond, respectively, to the following boolean formulas:
1. `not (A || B)`
2. `(not A) && (not B)`
3. `not (A && B)`
4. `(not A) || (not B)`
Note that formulas 1 and 2 correspond to each other under [De Morgan’s laws](https://en.wikipedia.org/wiki/De_Morgan%27s_laws). The same is true for formulas 3 and 4. In other words, these formulas satisfy the equations
1. Given any `a :: Binary` and `b :: Binary`, `deMorg1 a b == deMorg2 a b`,
2. Given any `a :: Binary` and `b :: Binary`, `deMorg3 a b == deMorg4 a b`.
We will see in Exercise 4 a way to have Haskell check these equations
for you automatically.
## Examples
“`hs
*Main> bin2Bool (orBin (bool2Bin False) (bool2Bin False))
False
*Main> bin2Bool (orBin (bool2Bin True) (bool2Bin False))
True
*Main> bin2Bool (notBin (bool2Bin False))
True
*Main> bin2Bool (deMorg2 (bool2Bin True) (bool2Bin True))
False
“`
# Exercise 4 – Finite Types
## Background Material
Recall that it is not possible in general to have an instance of the `Eq` typeclass for function types `a -> b`. In this exercise, we explore a case where this is possible.
For this, we will use the following two typeclasses: the `Enum` typeclass, which is for types whose elements may be enumerated, and the `Bounded` typeclass, which is for types which have a maximal and minimal element. We wish to consider types which have both these properties. We can do this by defining a typeclass `Finite` as follows:
“`hs
class (Bounded a, Enum a) => Finite a
“`
Notice that normally when we define a class we define new operation for it. In this case we have an empty collection of new operations: we just want to put together all the operations from `Bounded` and `Enum` into a new class `Finite` which serves to better describe the types which wish to consider.
**Note**: The type `Int8` is part of the `Data.Int` module. If you are testing your functions in `ghci` and it complains that `Int8` is not in scope, you can bring it into scope with the line
“`hs
import Data.Int
“`
Alternatively, you can add this line to your `Assessed1.hs` file (at the top of the section which you are allowed to modify) so that it is imported automatically which you load the file into `ghci`.
## Implementation Task
Write an equality comparison function
“`haskell
equals :: (Finite a, Eq b) => (a -> b) -> (a -> b) -> Bool
equals = undefined
“`
for functions whose domain is a finite type.
## Examples
We can consider the negation operation of 8-bit integers:
“`hs
neg :: Int8 -> Int8
neg n = -n
doubleNeg :: Int8 -> Int8
doubleNeg n = – (- n)
“`
For these functions, we can use our equality comparison to get
“`hs
*Main> equals neg (\x -> x)
False
*Main> equals doubleNeg (\x -> x)
True
“`
We can also use our equality to verify the properties of the functions we implemented in Exercise 3:
“`hs
*Main> equals (uncurry deMorg1) (uncurry deMorg4)
False
*Main> equals (uncurry deMorg1) (uncurry deMorg2)
True
*Main> equals (bin2Bool . bool2Bin) (\x -> x)
True
*Main> equals (bool2Bin . bin2Bool) (\x -> x)
True
“`
**Note:** The use of the `uncurry` function is important for the first two lines to evaluate correctly.
# Exercise 5 – Roots
## Background Material
In mathematics, a *root* of a function `f` is a value `x` of the domain such that `f x = 0`.
## Implementation Task
For a function with a finite domain, implement a function
“`haskell
roots :: (Finite a , Num b, Eq b) => (a -> b) -> [a]
roots = undefined
“`
which computes the list of all roots of `f`.
## Examples
Let us consider the following functions as examples:
“`hs
f1 :: Int8 -> Float
f1 x = fromIntegral (x^2 + 1)
f2 :: Int8 -> Float
f2 x = fromIntegral (x^2 – 9)
f3 :: Int8 -> Int8
f3 x = x `mod` 11
f4 :: Int8 -> Int8
f4 x = (x `mod` 11)^2 – 9
f5 :: Int8 -> Int8
f5 x = (x `mod` 11)^2 – 8
f6 :: Int8 -> Int8
f6 x = (x `mod` 11)^2 – 16
“`
For the above listed functions, we have the following results:
“`hs
*Main> roots f1
[]
*Main> roots f2
[-125,-3,3,125]
*Main> roots f3
[-121,-110,-99,-88,-77,-66,-55,-44,-33,-22,-11,0,11,22,33,44,55,66,77,88,99,110,121]
*Main> roots f4
[-118,-107,-96,-85,-74,-63,-52,-41,-30,-19,-8,3,14,25,36,47,58,69,80,91,102,113,124]
*Main> roots f5
[]
*Main> roots f6
[-128,-117,-106,-95,-84,-73,-62,-51,-40,-29,-18,-7,4,15,26,37,48,59,70,81,92,103,114,125]
*Main>
“`