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
 Table of Contents
 PreLab Checklist
 Getting Started
 The Last Lab
 WarmUp
 WarmUp (for those that like math)
 Recursion
 Lists
 Types
 Higher Order
 Trees
 Advanced Exercises
PreLab 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/lab121100_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
> projectname
. 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/lab121100_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.
WarmUp
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 (3tuple), 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 wasTrue
. Try to define it in a single line without guards.threeDiff
: Returns true if all three inputs are different.
WarmUp (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 argumentsa,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 nondegenerate quadratic (that is, that \(a \neq 0\).) [Hint: Consider usingdiscriminate
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_{n1} + T_{n2} + T_{n3} & 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 (2tuple)
(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 midpoint 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 ofa
, and anInt
, 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 ofa
, an element of typea
, an indexInt
, 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 (2tuples), 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 fromrunLengthEncoding
, 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 ofa
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 typea
as input, and the second can take typeb
as input. Also takes an element of the sum ofa
andb
as input. If the input was of the formLeft a
, extract the variable of typea
and apply the first function. Otherwise, apply the second function to the argument inRight 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 thea
fromLeft a
. If the input wasRight 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 aslefts
, 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 writtensumApply
.]>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 (2tuple) 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 thatpolyEval [a0, a1, a2, ..., an] x = a0 + a1*x + a2*x^2 + ... an*x^n

hornerEval
: Same aspolyEval
, 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 twodimensional 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
straightline 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 citiesdistance :: 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.