[SOLVED] algorithm Haskell 1. Please submit exactly one Haskell file where the questions are separately by a com-

1. Please submit exactly one Haskell file where the questions are separately by a com-
ment line. Add the answers to additional questions as well as your Haskell outputs
where requested as comments.

2. Please put your group number, names and student numbers at the beginning of file.

3. Marks will be awarded for correct functionality, for good code quality, for complying
with the instructions above and if asked for presenting your work.

4.complying with the instructions includes: Submitting exactly 1 Haskell files that
compliles

5. readable presentable layout of the file. Code quality Having added comments where
requested.

6.

Question 1. a) Write a Haskell function average that computes the average of three
numbers. (Note: For simplicity you may use input type Float.) Add a function called
howManyAboveAverage1 that computes how many of these three numbers are above the
average. Give a second solution (howManyAboveAverage2) for this function which is differ-
ent in nature, i.e., uses an algorithm that is computationally different. Run your programs
with your student numbers, and include the Haskell call and the original output as a com-
ment into your solution.

b) The following demonstrates a method how you could check the correctness of your
programs: Add the following code to the top of your file import Test.QuickCheck and
write a function as below (please complete its type) that compares the two implementations
in a) of your howManyAboveAverage functions:

checkcorrectness x y z =

howManyAboveAverage1 x y z == howManyAboveAverage2 x y z

In the commandline then do the check by typing.

quickCheck checkcorrectness

Include the response of Haskell as a comment.

Question 2. Pizzeria Alfredo sells pizzas of an arbitrary size and with an arbitrary number
of toppings. The owner Alfredo wishes to have a program that allows to compute the selling
price of a pizza depending on its size (given by its diameter in cm) and the number of
toppings. The pizza base costs 0.001 per cm2 and the costs for each topping are 0.002
per cm2. Since Alfredo also wants to make some profit, he multiplies the costs of a pizza
by a factor 1.5. Can you help Alfredo with a suitable Haskell function?
Finally, add a second function concerned with the answer of the following: Pizza Bambini
(tomatoes, mozzarella, ham, salami, broccoli, mushrooms, 16 cm) is more expensive than
Pizza Famiglia (tomatoes, mozzarella, 32 cm)? Add your response as a comment, together
with a suitable Haskell output that justifies your response.

Question 3. Starting from the programs

divides :: Integer -> Integer -> Bool

divides x y = y mod x == 0

prime :: Integer -> Bool

prime n = n > 1 && and [not(divides x n) | x <- [2..(n-1)]]allprimes :: [Integer]allprimes = [x | x<- [2..], prime x]Define a function allprimesBetween:: Integer -> Integer -> [Integer] that pro-
duces all prime numbers between two bounds.
Next produce an infinite list primeTest:: [Bool] such that the nth position of the list
is True if n is prime, and False otherwise. Then, produce an infinite list such that the
nth position is the pair (n, b) where the value b is True if n is prime and False otherwise.
Finally, add a function primeTwins that, given n, computes how many prime twin pairs are
amongst the first n prime numbers. Use this to answer the question: How many prime twin
pairs are there amongst the first 2000 prime numbers? [Hint: a prime twin pair consists of
two prime numbers that have a difference of 2. Examples: (5,7), (11,13)]

Question 4. In cryptography, we often need exponentiation modulo a number n. Write a
(recursive) program expmod that takes integers M , e, n as input and computes

M e modn.

Note: the computation of the huge number M e can be avoided using the fact that the
modulo operation commutes with multiplication, in particular:

M (e+1) modn = ((M e modn) M) modn.

Implement an improved second version expmodfast using the observation that M2e =
(M e)2? Demonstrate your function with your student number as exponent. (Result as
comment!)

Question 5 (Petri dish). Implement a simulation of cells on a Petri dish as follows.
The dish is represented as a rectangular grid where each point is a cell. Each cell is either
alive or dead and has up to 8 neighbours:

2

The simulation evolves in steps and the fate of each cell is decided according to the following
rules:

1. A live cell, which

(a) has fewer than 2 live neighbours dies because of underpopulation,

(b) has 2 or 3 live neighbours lives,

(c) has more than 3 live nieghbours dies because of overpopulation.

2. If a cell is dead and has exactly 3 live neighbours, it becomes a live cell.

Examples (black = live, white = dead):

You should represent the grid as a list of lists of Bool, that is a list that contains rows of
cells. For the simulation implement the following:

a) a function valid :: [[Bool]] -> Bool which checks whether the given grid is valid.
A grid is valid if and only if it has a rectangular shape (lengths of all rows are the
same), and if it is at least 3 3.

b) a function showGrid :: [[Bool]] -> String that returns a string representation
of a grid and a function printGrid :: [[Bool]] -> IO () that prints the grid to
the terminal. You can use O to represent a live cell and . to represent a dead one.
Example output:

.OO.

..O.O..

O

..O.O..

.OO.

c) a function readGrid :: String -> [[Bool]] that reads a string representation of
a grid and returns the corresponding grid.

d) a collection of functions that implement the evolution of one grid state into another.
In particular, you need to implement the following functions:

neighbours :: [Bool] -> Int which takes a list of neighbours of a cell and
returns the number of live neighbours,

newCell :: Int -> Bool -> Bool which takes the number of neighbours of a
cell and the cell itself and decides if the cell is to live or die after the step, and

step :: [[Bool]] -> [[Bool]] which takes a grid and returns a new grid
which is a one step evolution of the old one. This function should make appro-
priate use of above two functions and we encourage you to break it down into
multiple smaller functions that you can test in isolation.

3

There are at least 2 ways you can approach walking the grid. As a hint, for both
approaches you will need to think about how to deal with boundary areas of the grid.
The step function has to validate the grid before processing it. If the grid is invalid,
it should return an error by calling error Invalid grid.

e) a function loadGridFile :: String -> IO [[Bool]] which reads a grid from the
given file. You can assume that the file contents were generated using showGrid.
Validate the grid after loading it and signal an error if it is invalid.

f) a function interactive :: IO () which asks the user for a file name, loads a grid
from the given file, prints it, and waits for user input. If the user presses Enter, the
function prints the next step in the evolution and waits for input again. If the user
writes exit (and presses Enter), then the function terminates.

g) improvements to the simulation. After you have completed the main simulation, you
may improve it. Here are some ideas choose one of them they are of increasing
difficulty (and marks). They should be implemented as new functions for example,
if you want to improve on interactive, name the improved function interactive1,
etc. Always include a comment about what the improvement is and how you ap-
proached the implementation, otherwise your improvement may be overlooked.

In interactive, allow the user to save the current grid in a file that the user
chooses.

In interactive, give the user the option to generate a random grid of a given
size, instead of loading it from a file.

The file format is quite inefficient and can be improved in a few ways. One way
is to specify the grid size and only the significant cells from the top and the left,
and then complete the grid after loading. E.g.,

..

.O.O.

..O.O

O.O..

.O.O.

..

can be represented as the 4 8 grid

.

.O.O

..O.O

O.O

.O.O

Another way of making the grid file format more efficient is based on the observa-
tion, that the files contain many repeating characters. This makes them suitable
for run-length encoding, that is an encoding where repeating sequences of charac-
ters are represented as the character and its count. E.g., HHHHaaaaaaaaaaaskell
can be represented as 4H11a1s1k1e2l or even 4H11aske2l. Write both an en-
coding and decoding function for grid representations. You can even identify
the grid file format by using different file name extensions.

Finally, here are some patterns that you can use to test your programs. Some of them are
stable (i.e., they dont change between steps), some of them oscillate, or move.

You may be asked to present your work in one of the labs following submission.

4