2021/10/12 下午1:16 Assignments/1 · main · mhe / FP Learning 2021 2022 · GitLab
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/tree/main/Assignments/1 1/8
Assignment 1
Tom de Jong authored 53 minutes ago
Name Last commit Last update
..
Assignment 1 53 minutes ago
Assignment 1 53 minutes ago
Assignment 1 53 minutes ago
Assignment 1 53 minutes ago
Assignment 1 53 minutes ago
README.md
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 and . Types.hs Assessed1-Template.hs
Copy the file to a new file called and write your solutions in . Assessed1-Template.hs Assessed1.hs 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 . Assessed.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 in the terminal (in the same folder as your
submission). ./presubmit.sh Assessed1
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 and are abiding by them, in order for your
submission to qualify.
assets
Assessed1-Template.hs
README.md
Types.hs
presubmit.sh
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/commit/2b771a411280cde9394a972cdc382c211c1e9a4f
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/tree/main/Assignments
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/commit/2b771a411280cde9394a972cdc382c211c1e9a4f
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/commit/2b771a411280cde9394a972cdc382c211c1e9a4f
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/commit/2b771a411280cde9394a972cdc382c211c1e9a4f
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/commit/2b771a411280cde9394a972cdc382c211c1e9a4f
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/commit/2b771a411280cde9394a972cdc382c211c1e9a4f
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/blob/main/Assignments/1/README.md
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/blob/main/plagiarism
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/tree/main/Assignments/1/assets
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/blob/main/Assignments/1/Assessed1-Template.hs
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/blob/main/Assignments/1/README.md
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/blob/main/Assignments/1/Types.hs
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/blob/main/Assignments/1/presubmit.sh
2021/10/12 下午1:16 Assignments/1 · main · mhe / FP Learning 2021 2022 · GitLab
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/tree/main/Assignments/1 2/8
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 (to be copied by you). Assessed1Template.hs
Replace the default function implementation of with your own function. undefined
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
checksum :: Integral a => [a] -> Bool
checksum = undefined
that takes as input a list of numbers and checks that
�. The list is 8 elements long
�. The sum of the numbers is divisible by 11.
The function should return if both of these conditions are met, and otherwise. True False
Examples
*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.
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)
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/raw/main/Assignments/1/assets/gol-average-example-1.png
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/raw/main/Assignments/1/assets/gol-average-example-2.png
2021/10/12 下午1:16 Assignments/1 · main · mhe / FP Learning 2021 2022 · GitLab
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/tree/main/Assignments/1 3/8
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 , defined as follows: avg
avg :: [Int] -> Int
avg ns = sum ns `div` length ns
Next, we can define our function by computing the averages of the RGB components of a list of colours: blend
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:
type Coordinate = (Int, Int)
type Cell = (Coordinate, Colour)
Using the standard functions and (which will be explained in later lectures) we can easily get the colour of a cell (specified by a
coordinate) in a grid. fromJust lookup
colourOf :: Grid -> Coordinate -> Colour
colourOf coord g = fromJust (lookup g coord)
To see an example, let’s add colours to the grid like this: glider
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:
code :: Colour -> String
code (r, g, b) = show r ++ “;” ++ show g ++ “;” ++ show b ++ “m”
escapeStart :: String
escapeStart = “\ESC[38;2;”
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/raw/main/Assignments/1/assets/glider-1.png
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/raw/main/Assignments/1/assets/glider-2.png
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/raw/main/Assignments/1/assets/glider-3.png
2021/10/12 下午1:16 Assignments/1 · main · mhe / FP Learning 2021 2022 · GitLab
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/tree/main/Assignments/1 4/8
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 by (where is colour) in the function. This
gives us: putChar ‘0’ putStr (colourStr c “0”) c printCell
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
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 in the lecture notes.
Examples
The example from above looks as follows: glider
*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))]
Let’s look at a more complicated example. The “glider gun” can be defined by the following grid:
which looks like
Stepping it once gives
After running this for a couple of steps we get the following configuration:
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
*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
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/blob/main/LectureNotes/Sections/Life.md#representing-the-board-and-step-function
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/raw/main/Assignments/1/assets/glider-gun-1.png
2021/10/12 下午1:16 Assignments/1 · main · mhe / FP Learning 2021 2022 · GitLab
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/tree/main/Assignments/1 5/8
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 that takes two boolean arguments and produces if at least one argument is , and otherwise.
Instead of implementing these logic functions on the values and of type , let’s instead implement them on binary digits using the type
defined as: orB :: Bool -> Bool -> Bool True True False True False Bool Binary
data Binary = Zero | One
deriving (Eq, Show, Bounded, Enum)
Of course the type is equivalent to the type . We can verify this by defining two functions and checking that: Binary Bool bin2Bool ::
Binary -> Bool bool2Bin :: Bool -> Binary
�. Given any , , x :: Bool (bin2Bool . bool2Bin) x == x
�. Given any , . 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. means ). b :: Binary (bool2Bin . bin2Bool) b ==
b (.) (f . g) x f (g x)
Implementation Tasks
(a) Implement the two functions
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
notBin :: Binary -> Binary
notBin = undefined
andBin :: Binary -> Binary -> Binary
andBin = undefined
orBin :: Binary -> Binary -> Binary
orBin = undefined
which correspond to the functions , and under the translation you wrote in part (a). This means that your implementations should satisfy
the following conditions: not && ||
�. Given any , , x :: Bool not x == bin2Bool (notBin (bool2Bin x))
�. Given any and , , x :: Bool y :: Bool x && y == bin2Bool ((bool2Bin x) andBin (bool2Bin y))
�. Given any and , . x :: Bool y :: Bool x || y == bin2Bool ((bool2Bin x) orBin (bool2Bin y))
(c) Implement four functions
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/raw/main/Assignments/1/assets/glider-gun-2.png
2021/10/12 下午1:16 Assignments/1 · main · mhe / FP Learning 2021 2022 · GitLab
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/tree/main/Assignments/1 6/8
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:
�. not (A || B)
�. (not A) && (not B)
�. not (A && B)
�. (not A) || (not B)
Note that formulas 1 and 2 correspond to each other under De Morgan’s laws. The same is true for formulas 3 and 4. In other words, these
formulas satisfy the equations
�. Given any and , , a :: Binary b :: Binary deMorg1 a b == deMorg2 a b
�. Given any and , . a :: Binary 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
*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 typeclass for function types . In this exercise, we explore a case where
this is possible. Eq a -> b
For this, we will use the following two typeclasses: the typeclass, which is for types whose elements may be enumerated, and the
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 as follows: Enum Bounded Finite
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 and into a new class which serves to better describe the types which wish to
consider. Bounded Enum Finite
Implementation Task
Write an equality comparison function
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:
https://en.wikipedia.org/wiki/De_Morgan%27s_laws
2021/10/12 下午1:16 Assignments/1 · main · mhe / FP Learning 2021 2022 · GitLab
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/tree/main/Assignments/1 7/8
neg :: Int8 -> Int8
neg n = -n
doubleNeg :: Int8 -> Int8
doubleNeg n = – (- n)
For these functions, we can use our equality comparison to get
*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:
*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 function is important for the first two lines to evaluate correctly. uncurry
Exercise 5 – Roots
Background Material
In mathematics, a root of a function is a value of the domain such that . f x f x = 0
Implementation Task
For a function with a finite domain, implement a function
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:
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:
*Main> roots f1
[]
*Main> roots f2
[-125,-3,3,125]
*Main> roots f3
2021/10/12 下午1:16 Assignments/1 · main · mhe / FP Learning 2021 2022 · GitLab
https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022/-/tree/main/Assignments/1 8/8
[-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>