# Assessed Assignment 3
## Marking table
The exercises are defined so that it is hard to get a first-class mark.
“`
1st class – 70 marks and above.
upper 2nd – 60-69 marks.
lower 2nd – 50-59 marks.
third class – 40-49 marks.
fail – 0-39 marks.
“`
## Question Parts
In order to mitigate the implications of having only 4 questions on
this assignment, we have decomposed the exercises on this assigment
into smaller implementation tasks with the aim of providing
more opportunities for partial credit.
We have also made the individual tasks independent of each other as much as possible. On the other hand, we certainly recommend that you try to use the work you have done in one task to make the following ones easier whenever you can.
## Preparation
* Do __not__ modify the files `Types.hs` and `Assessed3-Template.hs`.
* Copy the file `Assessed3-Template.hs` to a new file called `Assessed3.hs` and write your solutions in `Assessed3.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 `Assessed3.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 Assessed3` 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 `Assessed3-Template.hs` (to be copied by you).
– Replace the default function implementation of `undefined` with your own function.
## Exercise 1 – Sorting Cupcakes
### Background Material
[Adapted from [Hameer & Pientka 2018](https://www.cs.mcgill.ca/~bpientka/papers/learn-ocaml-icfp19.pdf)]
You work at a cupcake shop that has recently taken the step of migrating their operations to Haskell.
In the shop manual, a *recipe* is now represented as a list of ingredients (possibly containing duplicates), and a *cupcake* is represented as a recipe together with a price.
“`haskell
data Ingredient = Nuts | Gluten | Soy | Dairy deriving (Show, Eq)
type Recipe = [Ingredient]
data Price = P Int deriving (Show, Eq, Ord)
data Cupcake = CC Price Recipe deriving (Show, Eq)
“`
To improve customer experience, you need to write some functions to let clients quickly filter cupcakes by different criteria.
### Implementation Task
* Write a function
“`haskell
priceRange :: Price -> Price -> [Cupcake] -> [Cupcake]
priceRange = undefined
“`
such that `priceRange minPrice maxPrice cupcakes` returns just those `cupcakes` whose price is between `minPrice` and `maxPrice` (inclusive).
* Write a function
“`haskell
allergyFree :: [Ingredient] -> [Cupcake] -> [Cupcake]
allergyFree = undefined
“`
such that `allergyFree allergens cupcakes` returns just those `cupcakes` that do not contain any `allergens`.
### Examples
“`hs
*Main> priceRange (P 200) (P 300) [CC (P 200) [Soy], CC (P 250) [Dairy], CC (P 400) [Nuts,Gluten]]
[CC (P 200) [Soy],CC (P 250) [Dairy]]
“`
“`hs
*Main> allergyFree [Dairy,Nuts] [CC (P 200) [Soy], CC (P 250) [Dairy], CC (P 400) [Nuts,Gluten]]
[CC (P 200) [Soy]]
“`
## Exercise 2 – Cupcake Specs
### Background Material
You are tasked with assuring quality at the bakery for the cupcake shop.
Under normal operations, cupcakes are baked together in batches on a cupcake tin before being priced.
To improve quality control, you would like to add an additional step of checking that every tin satisfies some formal specification before it is baked.
You introduce the following types:
“`haskell
type Tin = [Recipe]
data Spec = And Spec Spec | Or Spec Spec | Not Spec | HasCup Int Ingredient deriving (Show,Eq)
“`
Such specifications are meant to be interpreted as follows:
* a tin satisfies the specification `And s1 s2` if it satisfies both `s1` and `s2`
* a tin satisfies the specification `Or s1 s2` if it satisfies either `s1` or `s2`
* a tin satisfies the specification `Not s` if it does not satisfy the specification `s`
* a tin satisfies the specification `HasCup k x` if the recipe at position `k` (using [0-indexing](https://en.wikipedia.org/wiki/Zero-based_numbering)) contains the ingredient `x`
### Implementation Task
* Write a function
“`haskell
isValidSpec :: Spec -> Tin -> Bool
isValidSpec = undefined
“`
Which verifies that the given specification is well-formed for the provided `Tin`. That is, the function should return `False` if the specification contains *any* statement of the form `HasCup k x` where `k` is out of bounds of the tin and `True` otherwise.
* Write a function
“`haskell
checkSpec :: Spec -> Tin -> Bool
checkSpec = undefined
“`
which takes a specification `s` and a tin `t` as inputs, and returns `True` just in case `t` satisfies the specification `s`, or else `False`. You may assume when writing this function that the spec is valid in the sense of the first part of this exercise.
### Examples
For example, the sample tin pictured below (image not to scale)
“`hs
sampletin :: Tin
sampletin = [[Nuts], [Dairy,Gluten], [], [Soy]]
“`
satisfies the specification
“`hs
And (HasCup 0 Nuts) (And (HasCup 1 Gluten) (And (Not (HasCup 2 Dairy)) (HasCup 3 Soy)))
“`
but does not satisfy the specification
“`hs
Or (HasCup 0 Dairy) (HasCup 1 Soy)
“`
Moreover, the two above specifications are valid, while the specifications
“`hs
And (HasCup 0 Nuts) (And (HasCup (-2) Gluten) (And (Not (HasCup 2 Dairy)) (HasCup 3 Soy)))
Or (HasCup 0 Dairy) (HasCup 4 Soy)
“`
are not.
## Exercise 3 – Navigating a Directory Structure with Breadcrumbs
### Background
Recall the simple directory structure data type we developed in the Lab sessions:
“`haskell
data File = File {
fileName :: String,
fileContents :: String
} deriving (Eq,Show)
data Directory = Dir {
dirName :: String,
dirContents :: [ DirectoryEntry ]
} deriving (Eq,Show)
data DirectoryEntry =
FileEntry File
| DirEntry Directory
deriving (Eq,Show)
“`
In this exercise, we will develop an auxillary data type for
*navigating* the directory structure. The idea will be that
we can “enter” a subdirectory by keeping the list of entries
above and below the subdirectory we choose. We represent this
by the type `EnteredDirectory`.
“`haskell
data EnteredDirectory = ED {
entriesBefore :: [DirectoryEntry],
enteredDirName :: String,
entriesAfter :: [DirectoryEntry]
} deriving (Eq, Show)
“`
Now we will say that a `Breadcrumb` is a pair of a directory
(the one we are currently “looking at” which we will call the **focus**) and a list of entered
directories (the ones we have passed to get to our current subdirectory).
“`haskell
type Breadcrumb = (Directory , [ EnteredDirectory ])
“`
### Implementation Task
* Write a function
“`haskell
parentDir :: Breadcrumb -> Maybe Breadcrumb
parentDir = undefined
“`
which passes to the parent directory (if one exists) and
returns `Nothing` if we are at the root.
* Write a function
“`haskell
openSubDir :: String -> Breadcrumb -> Maybe Breadcrumb
openSubDir = undefined
“`
which takes a directory name and attempts to find it in the currently focused
directory, making it the new focus. The function should return `Nothing` if
the subdirectory cannot be found.
### Examples
Let’s suppose our directory contains recipes organized by country and
region like this:
“`
recipes
├── italian
│ ├── lasagna.txt
│ └── pizza.txt
├── american
│ ├── hot-dogs.txt
│ ├── burgers.txt
│ ├── tex-mex
│ │ ├── chimichanga.txt
│ │ └── burrito.txt
│ └── southern
│ ├── fried-green-tomatoes.txt
│ └── shrimp-and-grits.txt
└── french
├── crepes.txt
└── quiche.txt
“`
You can find the above directory structure written out
[here](./Q3Example.hs). Additionally, there are some example
`Breadcrumb`’s for you to play with. In the examples which follow,
the output has been simplified using the names of files and
directories in the previously linked file. (This avoids a lot of
clutter, and will help to convey the general idea).
Now, when focused on the root of this hierarchy, we simply have the following
`Breadcrumb`:
“`hs
(recipes , [])
“`
If we now focus on the `american` subdirectory, this becomes
“`hs
(american , [ ( [ DirEntry italian ] , “recipes”, [ DirEntry french ]) ])
“`
Notice how the entries at the same level as the `american` subdirectory are split
into the list of those appearing before the focus, and those appearing after.
Focusing one level further, on the `tex-mex` subdirectory, we should see
“`hs
(texMex , [ ( [ FileEntry hotDogs, FileEntry burgers ] , “american” , [ DirEntry southern ]) ,
( [ DirEntry italian ] , “recipes” , [ DirEntry french ]) ])
“`
Our `Breadcrumb` therefore, keeps track of where we *are* (i.e. `texMex`) and where we’ve *been* (i.e. `recipes` and `american`) while at the same time always allowing us to recontruct the entire directory structure.
Again referring to the [example file](./Q3Example.hs), we have the following equations:
“`hs
*Main> parentDir bc1 == Just bc2
True
*Main> openSubDir “french” (recipes , []) == Just bc0
True
“`
## Exercise 4 – Prime Number Sieve
### Background
Please first read the Wikipedia page on the [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).
The main goal of this question is define an infinite list of booleans
“`hs
sieve :: [Bool]
“`
such that, for any given `n ≥ 2`, we have `sieve !! (n-2) = True` if and only if `n` is prime. The beginning of this infinite list looks like this:
“`hs
— position 0 1 2 3 4 5 6 7 8 9 …
— Eratosthenes index 2 3 4 5 6 7 8 9 10 11 …
sieve = [ True, True, False, True, False, True, False, False, False, True, …
“`
**A Note on Indexing:** We normally index the elements of a list starting from zero. For example
“`hs
[“abc”, “xyz” , “uvw”] !! (-1) = undefined
[“abc”, “xyz” , “uvw”] !! 0 = “abc”
[“abc”, “xyz” , “uvw”] !! 1 = “xyz”
[“abc”, “xyz” , “uvw”] !! 2 = “uvw”
[“abc”, “xyz” , “uvw”] !! 3 = undefined
“`
Recall that `(!!)` is the prelude function
“`hs
(!!) :: [a] -> Int -> a
“`
that given a list `xs` and a position, or index, `n`, gives the `n`th element of `xs` if it exists, and is `undefined` otherwise.
For defining the Sieve of Eratosthenes, it will be convenient to index
the elements starting from 2, the first prime number. This is easily
achived by using the function `(!!)` after subtracting 2, as in
“`hs
xs !! (n-2)
“`
We call `n` a *position* in the list and `n-2` an *Eratosthenes index*.
### Implementation Tasks
* Write a function
“`haskell
cross :: Int -> [Bool] -> [Bool]
cross = undefined
“`
such that for every `n ≥ 2` and every infinite list `xs` and, we have that `cross n xs` crosses out the elements of `xs`, by setting them to `False`, every `n` elements, starting from position `n-1` and keeping all other positions as they are in the list `xs`.
* Write a function
“`haskell
sieveFrom :: Int -> [Bool] -> [Bool]
sieveFrom = undefined
“`
such that we can define
“`haskell
sieve :: [Bool]
sieve = sieveFrom 2 (repeat True)
“`
In other words, `sieveFrom n` should be the transformation we need to make to our infinite list as we pass the number `n`.
* Write a function
“`haskell
sequenceFrom :: Int -> [Bool] -> [Int]
sequenceFrom = undefined
“`
such that that the list of all prime numbers can be given as
“`haskell
primes :: [Int]
primes = sequenceFrom 2 sieve
“`
## Examples
For the `cross` function, we should see
“`hs
*Main> take 20 (cross 2 (repeat True))
[True,False,True,False,True,False,True,False,True,False,True,False,True,False,True,False,True,False,True,False]
*Main> take 20 (cross 3 (repeat True))
[True,True,False,True,True,False,True,True,False,True,True,False,True,True,False,True,True,False,True,True]
*Main> take 20 (cross 4 (repeat True))
[True,True,True,False,True,True,True,False,True,True,True,False,True,True,True,False,True,True,True,False]
*Main> take 20 (cross 5 (repeat True))
[True,True,True,True,False,True,True,True,True,False,True,True,True,True,False,True,True,True,True,False]
“`
Here `repeat True` is the infinite list whose elements are all `True`.
Here are some examples of the `sequenceFrom` function:
“`hs
*Main> take 20 (sequenceFrom 2 (cross 5 (repeat True)))
[2,3,4,5,7,8,9,10,12,13,14,15,17,18,19,20,22,23,24,25]
*Main> take 20 (sequenceFrom 2 (cross 2 (repeat True)))
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]
*Main> take 20 (sequenceFrom 3 (cross 2 (repeat True)))
[3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41]
*Main> take 20 (sequenceFrom 4 (cross 2 (repeat True)))
[4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42]
*Main> take 20 (sequenceFrom 2 (cross 3 (repeat True)))
[2,3,5,6,8,9,11,12,14,15,17,18,20,21,23,24,26,27,29,30]
*Main> take 20 (sequenceFrom 3 (cross 3 (repeat True)))
[3,4,6,7,9,10,12,13,15,16,18,19,21,22,24,25,27,28,30,31]
*Main> take 20 (sequenceFrom 4 (cross 3 (repeat True)))
[4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26,28,29,31,32]
“`
Recall that once we have the `sequenceFrom` function, we can define the `sieve`.
“`hs
sieve :: [Bool]
sieve = sieveFrom 2 (repeat True)
“`
Moreover, we can now check if a number is prime:
“`hs
isPrime :: Int -> Bool
isPrime n = sieve !! (n-2)
“`