Week 12: Exam Prep

In this lab we recap the course, and provide lots of exercises for you to work on with your peers to help prepare for the final exam.

Table of Contents
Pre-Lab Checklist
Getting Started
The Last Lab
Warm-Up
Warm-Up (for those that like math)
Recursion
Lists
Types
- Sum
- Apollo Construction Company
Higher Order
- Using Higher Order functions
- Defining higher order functions
Trees
- Family Trees
Advanced Exercises

Pre-Lab Checklist

You have made a solid attempt at all other labs in this course.
You should have read back through the other labs, and have any problems that you struggled with or questions that you have at the ready.

Getting Started

Go to the project’s dashboard under the Project tab and click on the Fork button. The gitlab url for this lab is https://gitlab.cecs.anu.edu.au/comp1100/2023s2/studentfiles/lab12-1100_s2_2023
You will be asked where to fork the repository. Click on the user or group to where you’d like to add the forked project. You should see your own name here. Once you have successfully forked a project, you will be redirected to a new webpage where you will notice your name before > project-name. This means you are now the owner of this repository. The url in your browser should reflect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/lab12-1100_s2_2023
Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.
There will be a collection of exercises, sorted into files based on different topics covered in this course. Spend your time on the topics you have most difficulty with.

The Last Lab

Congratulations on making it this far! We hope you’ve picked up a lot during this course. This lab will not cover any new content, but will provide you with an opportunity to work on some more exercises, and prep for the exam.

There are too many exercises in this lab for you to do all of them. Concentrate on the exercises that are related to the material that you think you need the most practice with.

You could find other people in your lab who wish to work on the same problems as you, and work together. We highly encourage the use of writing code together on whiteboards in this lab, rather than at a computer by yourself.

You may also wish to spend this time revisiting a previous lab that you struggled with if you prefer.

Note that this lab does not require submission via git. The participation marks for this lab are earned by your tutor observing you working on lab exercises. What this lab isn’t is a place for you to work on your assignment. These are to be done in your own time, as your tutors usually cannot help you with your assignment code anyway.

Warm-Up

Put your work in Warmup.hs

For some of these functions, the types are not provided. You’ll have to work them out yourself.

bigThree: Takes three arguments, and returns the biggest.
middle: Take as input a triple (3-tuple), and returns the middle element.
isVowel : Takes in a character, and checks if the character is a vowel. A vowel is one of the following letters: a,e,i,o,u.
xor : Takes two Boolean’s, and returns true if one and only one of the inputs was True. Try to define it in a single line without guards.
threeDiff : Returns true if all three inputs are different.

Warm-Up (for those that like math)

Put your work in Warmup.hs

discriminate : Takes in three arguments, a,b,c and returns the discriminate \(D\) of the quadratic equation \(ax^2 + bx + c = 0\), defined as \(D = b^2 - 4ac\)
rootsQuad : Takes in three arguments a,b,c and will return any real roots of the equation \(a x^2 + bx + c = 0\). You must not throw an error if only one or zero real roots exist. It should be possible to use your function to figure out how many roots there are, and then also obtain those root(s) (if they exist.) As a reminder, the quadratic formula is \(\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\) You may assume that this is a non-degenerate quadratic (that is, that \(a \neq 0\).) [Hint: Consider using discriminate to figure out how many real roots there are.]

Recursion

Put your work in Recursion.hs

Tribonacci

Write a function that computes the tribonacci sequence \(T_n\), defined as \(T_n = \begin{cases} 0 & n = 0 \\ 0 & n = 1 \\ 1 & n = 2 \\ T_{n-1} + T_{n-2} + T_{n-3} & n \geq 3 \end{cases}\)

Check that the first few terms are \(0,0,1,1,2,4,7,13,24,44,81,\ldots\)

Your solution should be efficient, and you should have no trouble computing \(T_{100}\) in under a second.

Chessboard

chessboard : Write a function that takes in a pair (2-tuple) (n,m), and returns a list of all cells from (1,1) to (n,m). The order is not critical.

> chessboard (2,3)
[(1,1),(2,1),(1,2),(2,2),(1,3),(2,3)]

Square Roots by Bisection

There are many ways to compute square roots, and here we investigate the method of bisection. Given a number \(n\), it’s obvious that that \(0 \leq \sqrt{n} \leq n\). As an initial guess, we suppose that the square root of \(n\) is \(n/2\). We square the result, and if it’s too big, then we know that the square root lies in the interval \([0,n/2]\). Otherwise, it lies in the interval \([n/2,n]\). We take the mid-point of our interval as our next guess, and repeat.

For example, to compute \(\sqrt{2}\).

Our initial interval is \([0,2]\).
We guess \(\sqrt{2} \approx 1\), but \(1^2 = 1 < 2\), so we guessed too low.
New interval is \([1,2]\).
Guess \(\sqrt{2} \approx 1.5\), but \(1.5^2 = 2.25>2\), so we guessed too high.
New interval is \([1,1.5]\).
Guess \(\sqrt{2} \approx 1.25\), etc.

Using this algorithm, try to write a function that computes the square roots of functions in this manner. Terminate when the interval is sufficiently small, and we have computed \(\sqrt{n}\) to sufficiently high precision.

Lists

Put your work in Lists.hs

You may use higher order functions like map,foldr,filter,zipWith, but do not use predefined functions if it makes the question trivial to solve (implementing a sort using sort, for instance).

isSorted : Checks if a list is sorted from smallest to biggest.
insertSorted : Assuming that the input list is sorted, takes an element and inserts it into the list in the correct place, so that the list is still sorted.
removeDup : Takes a list, and deletes any elements that have already appeared in the list so far.
```
>removeDup [2,5,2,4,4,1,7,8,2,4,6,3]
[2,5,4,1,7,8,6,3]
```
(Don’t use nub to help you.)
continuous : Takes a list of integers, and checks that each element in the list is at most one away from the previous element
```
> continuous [1,2,3,3,2,3,4,3,2]
True
> continuous [3,4,3,5,4] -- jumps from 3 to 5
False
```
rotate : Takes a list of a, and an Int, and rotates the elements of the list around by the number indicated.
```
>rotate [1,2,3,4] 1
[2,3,4,1]
>rotate [5,6,7,8,9,10] 3
[8,9,10,5,6,7]
>rotate "abcdefg" (-2)
"fgabcde"
```

insertAt : Takes a list of a, an element of type a, an index Int, and inserts that element into the list at that element.

>insertAt "abcdef" '$' 0
"$abcdef"
>insertAt "abcdef" '$' 3
"abc$def"
>insertAt "abcdef" '$' (-1)
"abcdef$"
>insertAt "abcdef" '$' (-2)
"abcde$f"

runLengthEncoding : Takes a list, and returns a list of pairs (2-tuples), counting how many times that element was duplicated consecutively.

>runLengthEncoding "aaabbccccddcccaaaab"
[('a',3),('b',2),('c',4),('d',2),('c',3),('a',4),('b',1)]
>runLengthEncoding [2,2,1,4,4,2,3,2,2,3]
[(2,2),(1,1),(4,2),(2,1),(3,1),(2,2),(3,1)]

runLengthDecoding : Take the output from runLengthEncoding, and reconstruct the original string.

>runLengthEncoding [('a',3),('b',2),('c',4),('d',2),('c',3),('a',4),('b',1)]
"aaabbccccddcccaaaab"
>runLengthEncoding [(2,2),(1,1),(4,2),(2,1),(3,1),(2,2),(3,1)]
[2,2,1,4,4,2,3,2,2,3]

transpose : Take a list of lists of a as input, and transpose it (swap rows with columns).
```
>transpose [[1,2,3],[4,5,6],[7,8,9]]
[[1,4,7],[2,5,8],[3,6,9]]
```

Types

Put your work in Types.hs

Sum

We’ve defined a new data type to try and emulate the sum of two sets you’ve see in lectures before.

data Sum a b = Left a | Right b
    deriving Show

This data types takes two type variables a and b, and can be either Left a or Right b.

Work out the types of the following functions, and then implement them.

sumApply: Takes two functions, the first can take type a as input, and the second can take type b as input. Also takes an element of the sum of a and b as input. If the input was of the form Left a, extract the variable of type a and apply the first function. Otherwise, apply the second function to the argument in Right b.

[Hint: What must the output types of both functions be?]
```
>sumApply length (*2) (Left "hello")
5
>sumApply length (*2) (Right 10)
20
```
fromLeft : Takes an element of a sum, and extracts the a from Left a. If the input was Right b, throw an error.
```
>fromLeft (Left "hello")
"hello"
>fromLeft (Right 9)
-- an error is thrown
```

fromRight : Same as above, but return the second.

>fromRight (Left "hello")
-- an error is thrown
>fromRight (Right 9)
9

lefts : Takes a list of elements of a sum, and returns a list containing only the left elements.

rights : Same as lefts, but returns only the right elements.

> lefts [Left "hello", Right 5, Left "world", Right 10]
["hello", "world"]
> rights [Left "hello", Right 5, Left "world", Right 10]
[5, 10]

sumMap : Takes a list of elements of a sum, and two functions, and maps the appropriate function onto each element. [Hint: This function should be easy once you’ve written sumApply.]
```
>sumMap length (*2) [Left "yes", Right 7, Left "no", Right 9]
[3,14,2,18]
```
sumExtract : Takes a list of elements of a sum, and returns a pair (2-tuple) of lists as shown.
```
>sumExtract [Left "yes", Right 7, Left "no", Right 9]
(["yes", "no"],[7,9])
```

What could be some useful applications of this new datatype?

Apollo Construction Company

A newly founded construction company, the Apollo Construction Company (ACC), needs your help in developing some software to keep track of it’s workers.

Every worker has a name, an age, and a job.

data Job = Digger | Driver | Builder | Foreman | Manager 
  deriving Show
data Worker = Worker Name Age Job
  deriving Show
type Name = String
type Age = Int

A crew is a list of workers.

data Crew = [Worker]
  deriving Show

apolloCrew :: Crew 
apolloCrew = [Worker "Alice" 26 Driver,
      Worker "Bob" 21 Digger,
      Worker "Charlie" 34 Foreman,
      Worker "Daniel" 24 Digger,
      Worker "Eve" 31 Builder,
      Worker "Frank" 38 Manager,
      Worker "Grace" 34 Builder]

The ACC has asked you to work out how to code the following functions.

reassign : Takes a worker, and gives them a new job.

reassign (Worker "James" 35 Digger) Driver
> (Worker "James" 35 Driver)

birthday : A worker has had a birthday today! Increase their age by one.

birthday (Worker "Rachael" 23 Foreman)
> (Worker "Rachael" 24 Foreman)

isOnCrew : Checks if a particular worker is on a crew.

isOnCrew "Sal" apolloCrew
> False
isOnCrew "Eve" apolloCrew
> True

findSenior : Finds and returns the name of the most senior (oldest) worker on a crew.

findSenior apolloCrew
> "Frank"

filterJob : Given a crew, returns all workers that match a given job.

filterJob apolloCrew Digger
> [Worker "Bob" 21 Digger, Worker "Daniel" 24 Digger]

The ACC now needs to come up with a way to store the hourly wages for each worker (based on their job).

Find a sensible definition for PayRate that associates with each job an hourly wage (some Integer number of dollars)

Then, based on your definition, define

apolloWages :: PayRate

that assigns the pay rates according to this table

Job	Pay Rate
Digger	20
Driver	25
Builder	40
Foreman	80
Manager	120

crewCost : Given a crew, and a pay rate, and a number of hours, determines how much it would cost to hire the crew for that duration of time.

crewCost apolloCrew apolloWages 8
> 2760

Higher Order

Put your work in HigherOrder.hs

Using Higher Order functions

Implement the following functions using higher order functions. Your solutions should be very succinct, and should not use recursion (other than the recursion provided by a higher order function).

The following functions all take a list of numbers as their input; for our definitions we will refer to this list as \(x_1, x_2, \ldots, x_n\).

arithMean : Computes the average of a list of numbers. \(\frac{x_1 + x_2 + \ldots + x_n}{n}\)
geoMean : Computes the geometric mean of a list of numbers. \(\sqrt[n]{x_1 x_2 \ldots x_n}\)
l1Norm : Takes a list of numbers, and computes the sum of the absolute values of each term. \(|x_1| + |x_2| + \ldots + |x_n|\)
l2Norm : Takes a list of numbers, and computes the Eucledian norm, defined to be the square root of the sum of the squares of each element. \(\sqrt{x_1^2 + x_2^2 + \ldots + x_n^2}\)
cesaroSum : Given a list \(x_1, x_2 ,\ldots, x_n\), computes the \(\text{Ces\'aro}\) summation, given by returning a new list \(a_1,a_2,\ldots a_n\), where \(a_k = \frac{1}{k} \sum_{i=1}^k x_i\)

That is, \(a_k\) is the average of the first \(k\) terms of the input list.

Defining higher order functions

revMap : Takes an element, and feeds that element to each function in a list

> revMap 3 [(+1), (*2), (^2)]
[4,6,9]
> revMap 5 [(>3), (==4), (==5)]
[True, False, True]

superMap : Takes a list of elements, and a list of functions, and applies each element to each function. Your output should be a list of lists.
```
> superMap [3,5] [(+1), (*7), (^2)]
[[4,21,9],[6,35,25]]
```

Trees

Put your work in Trees.hs

If you haven’t completed Lab 09 or Lab 10 then you should finish them before doing the following exercises.

Recall the definition of a binary search tree:

data BSTree a = Null | Node (BSTree a) a (BSTree a)

Recall that a binary tree satisfies the binary search ordering constraint, if either:

It is a Null tree
Every element in the left hand subtree is strictly less than the root, and every element in the right hand subtree is strictly more than the root. Furthermore, both subtrees also satisfy the binary search ordering constraint.

You may find the functions you wrote in labs 9 and 10 helpful here.

What does the following function do?

treeMystery :: BTree a -> BTree a
treeMystery tree = case tree of
    Null -> Null
    Node left x right -> Node (treeMystery right) x (treeMystery left)

Family Trees

We’d like to encode a family tree as a binary tree, with a person at the top root node, and their father on the left sub tree, and their mother on the right subtree. We repeat this process all the way up, fathers on left, mothers on right.

We also create a new data type to encode the ancestor of a person:

data Person = Me | My Ancestor
data Ancestor = Father | Mother | Grand Ancestor 
type FamilyTree = BinaryTree Name
type Name = String

So a person is either Me (the person at the top of the family tree), or that person’s ancestor.

I’ve included my family tree (or, at least as much of it that I could find out) and the family tree of Prince George, the youngest first born child of the British royal family. (You’ll note that royal family trees usually only bother to keep track of the royal bloodline, those with a direct lineage to William I, the “first” king of England. Our data structure is actually insufficient for messy family trees like this one, but it will suffice.)

Your goal is to write some functions that operate on family trees.

ancestors :: Person -> FamilyTree -> [Name]

Given a family tree and the description of an ancestor (e.g., grandmother) return all of those ancestors.

> ancestors Me david
["David Quarel"]
> ancestors (My Mother) david
["Helen Corcoran"]
> ancestors (My (Grand Father)) david
["Luigi Quarel", "Mark Corcoran"]
> ancestors (My (Grand (Grand Mother))) david
["Rosa Randazzo","Assunta Karsun","Mary O'Sullivan","Charlotte Ohlin"]

kindAncestor :: FamilyTree -> Name -> Maybe Person

Given a family tree and a name, return what kind of ancestor they are, if they can be found.

> kindAncestor david "David Quarel"
Just Me
> kindAncestor david "Helen Corcoran"
Just (My Mother)
> kindAncestor david "Luigi Quarel"
Just (My (Grand Father))
> kindAncestor david "Alan Turing"
Nothing
> kindAncestor george "Elizabeth II"
Just (My (Grand (Grand Mother)))

The second test verifies that one of George’s great grandmothers (on his father’s father’s side) is the current British monarch, Queen Elizabeth II.

Advanced Exercises

Put your work in Advanced.hs

Polynomial Evaluation

polyEval : Takes a list of doubles representing coefficients of a polynomial sorted from lowest to highest degree, and a double \(x\). Evaluates the polynomial at that point \(x\). The result should be that
```
polyEval [a0, a1, a2, ..., an] x = a0 + a1*x + a2*x^2 + ... an*x^n
```
hornerEval : Same as polyEval, but use the following identity (called Horner’s Rule) to evaluate the result efficiently): \(a_0 + a_1 x + a_2 x^2 + a_3 x^3 = a_0 + x \left( a_1 + x \left( a_2 + a_3 x \right) \right)\). This identity generalises to a polynomial of any degree.

Primes

isPrime : Takes in an integer, and checks if it is prime. As a reminder, a prime number is a positive number that has two unique divisors, itself and one. The first few primes are: \(2,3,5,7,11,13,17,19,23\ldots\)

How can this function be written efficiently?
factor : Takes in an integer, and returns a list of its prime factors (counting primes more than once if necessary).
```
>factor 60
[2,2,3,5]
>factor 1050
[2,3,5,5,7]
>factor 391
[17,23]
>factor 83
[83]
```

Travelling Salesperson Problem (TSP)

Given a collection of cities in a country, a travelling salesperson would like to visit all the cities, and get back to the start, while travelling the least total distance (as the cost of fuel eats into his budget).

Each city is represented by a point on a two-dimensional grid describing where the city is.

type City = (Double, Double)
type Route = [City]

Given three cities at (0,0), (1,0), (0,1), they form a triangle, and it’s obvious that the best solution is to start at one city, visit the second, visit the third, and then go back to the first city. But for many cities, there might be many possibly routes to take, and some will be quicker than others.

We measure the cost to travel between two cities via Eucledian straight-line distance. So the cost to travel from city (0,0) to city (1,1) is \(\sqrt{1^2 + 1^2} = \sqrt{2}\).

tsp : Takes in a list of cities, represented by pairs (Double,Double), and returns the coordinates rearranged in the order the travelling salesperson should visit them to minimise travel cost.

You may find it useful to write the following helper functions:

cost returns the total distance travelled along a particular route.

cost :: [City] -> Distance

> cost [(0,0),(1,1),(2,1)]
2.414213562373095

distance returns the distance betwen two cities

distance :: City -> City -> Distance

> distance (0,0) (1,1)
1.4142135623730951

> tsp [(0,0),(2,3),(1,4),(2,2),(1,5),(1,3),(3,3),(2,4)]
[(0.0,0.0),(1.0,3.0),(1.0,4.0),(1.0,5.0),(2.0,4.0),(2.0,3.0),(3.0,3.0),(2.0,2.0),(0.0,0.0)]

Your answer may vary from the above, depending on which city you start and end at. But the total distance over the route should be the same as mine.

> cost (tsp [(0,0),(2,3),(1,4),(2,2),(1,5),(1,3),(3,3),(2,4)])
12.81913190966076

If you’re taking or have taken MATH1005, you might recognise this problem as a special case of finding a Hamiltonian circuit for a graph.

Table of Contents