CS计算机代考程序代写 Haskell 2021/10/12 下午1:16 Assignments/1 · main · mhe / FP Learning 2021 2022 · GitLab

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>