COMP1100/1130 [2020 S1]:
PROGRAMMING AS PROBLEM SOLVING Research School of Computer Science
Menu
menu
» Labs » Week 5: Recursion and Lists
In this lab we learn about the concept of recursion, which gives us the ability to “loop”, or repeat the same instruction many times over. We also investigate our Urst recursive data type, lists, that can pack many instances of a type together. We will write recursive functions over integers and lists.
Table of Contents
Pre-Lab Checklist
Recursion
UndeUned Behaviour and InUnite Loops Lists
Constructing Lists
List Patterns
Functions on Lists
Extensions
Pre-Lab Checklist
You should have Unished and submitted Lab 4.
You are comfortable with writing simple functions using guards.
You know what case statements and patterns are, and how to use them.
Getting Started
1. 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/2020s1studentUles/lab05
2. 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 re`ect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/lab05
3. Finally, clone your forked repository to your computer according to the instructions in the Week 2 Lab.
4. Put your exercise solutions in the Ule Lab05.hs. This Ule is pre-Ulled with unUnished functions that match the exercises below.
Recursion
Recursion is a concept borrowed from mathematics where a function is deUned in terms of itself. This sounds circular, but it’s a very powerful tool, and it gives us the ability to create loops in our programs to repeat an operation over and over again.
The Factorial Function
The factorial of some number n, denoted n!, is the product of all positive whole numbers less than or equal to n.
n! = { 1 n = 0
n × (n − 1)! otherwise
We deUne 0! = 1 by convention.
Note that the factorial function is deUned in terms of itself, which makes it a recursive
function.
Recursively deUned mathematical functions are very easily translated into Haskell. The deUnition of the factorial function acts in one of two ways, depending if the input is zero or not. So we need to check which case it is, and we can do so using guards.
Now how factorial appears in the deUnition of factorial, just as it does in the original deUnition above.
Almost all recursive functions follow a similar pattern, by deUning the function for the “Urst”, or the “simplest” input, called the base case, and then deUning the function for all other inputs recursively. We call this the step case.
For the case of the factorial function, the base case is deUning 0! = 1, and the step case is deUning n! = n × (n − 1)! for all numbers larger than zero.
For this lab, put all your answers in the Ule Lab05.hs provided. Exercise 1
(Hint: Think about what the value of sumNumbers 0 should be.) Submission required: Exercise 1 sumNumbers
UndeUned Behaviour and InUnite Loops
The factorial function is only deUned for non-negative numbers. But as written, there’s nothing stopping you from calling the function with a negative input.
Try running factorial (-1) and see what happens.
It’s pretty clear that this code isn’t going to terminate. (If you did run it and it’s trapped in an inUnite loop, hit Ctrl+C to tell Haskell to give up and stop trying to evaluate it.)
So what happened there? The argument decreases by one after each loop iteration, but because the base case is at zero, and we started at a negative number, the function will never stop calling itself (until either the user intervenes, or the program crashes due to consuming all the resources.)
Exercise 2
As a reminder, you can return an error by calling the error function, and giving it a string to print. Try to make the error message short but informative.
Submission required: Exercise 2 Invalid Input Exercise 3
Submission required: Exercise 3 rangeSum Exercise 4
Submission required: Exercise 4 rangeSumEx Exercise 5
The Fibonacci sequence Fn is as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, … The pattern that the sequence follows is that the Urst two terms are deUned to be zero and one respectively, (F0 = 0, F1 = 1) and then each successive term is the sum of the previous two.
As a test, verify that F30 = 832040.
Lists
Lists are very useful for storing a sequence of elements, all of the same type. An informal deUnition of lists in Haskell looks like
data [a] = [] | a : [a]
which is to say, a list containing elements of type a is either:
An empty list, []
An element of type a, attached using : onto the front of another list [a].
The element is attached using the operator : (pronounced “cons”, short for construct). We sometimes say a is “cons-ed” onto the list [a].
Note that the deUnition of list contains itself, just like the deUnition of a recursive functions contains itself. This is why a list is an example of a recursive data structure.
Now the important thing here to note is that the type a is arbitrary, it can be any type that has values. You could have [Integer] or [Bool], for instance. You can even put tuples [(Int,String)] or maybe types [Maybe Char] or even functions [Int -> Bool] in lists! You can even have lists inside other lists! [[Integer]], [[[Bool]]].
Examples of Lists
If we wanted the list containing 1, then 2, then 3, we would represent that as
1:(2:(3:[]))
Haskell has a nice shorthand way of writing this as [1,2,3]. Remember that writing lists in this compact form is identical to the above form. 1:[2,3] and 1:(2:[3]) are also equivalent.
In fact, the brackets above are unnecessary, as : is a right-associative operator, that is, given the expression x:y:xs, Haskell will automatically evaluate it right-to-left, resulting in x:(y:xs).
Hence, we could write the list of the Urst three numbers as 1:2:3:[]. Constructing Lists
Suppose we want to write a function, copy, that takes two arguments, an Integer n, and a Char c. We want to return a String that is made up of that same character c, repeated n many times.
This time we are recursing over the input integer n, and building a list as we go.
The base case here is when n is zero. We want zero copies of c, so we can return an
empty list.
copy 0 c = []
Now if n isn’t zero, that means we need at least one more copy of c. So we cons another c onto all the other copies of c. What function creates all the other copies of c? copy does! We then decrease n by one, to indicate how many more copies we need.
copy n c = c : copy (n-1) c
(It’s also sensible to reject the input if n is negative, as I cannot have negatively many
copies of something.) Putting it all together,
Exercise 6
Submission required: Exercise 6 rangeList List Patterns
Sometimes, rather than constructing new lists, we would like to write functions that operate on lists given as input. To write functions that operate on lists, we use pattern matching (see Week 3 Lab if you need a refresher on pattern matching). Usually, we use patterns to match against the shape of a list, rather than it contents.
Here is a list of useful patterns that you might need:
Functions on Lists
Now that we know how to match against a list, let’s try write some functions over lists. Lists are a recursively deUned data type, so if we need to visit every element in the list (which we don’t always have to do), then we should write our functions in a recursive manner. By deUnition, every list is either empty, [], or a list with at least one element x:xs, so these will usually (but not always!) be our base and step cases respectively.
We will consider the function sumList, which takes a [Integer], and returns the sum of all the integers in the list.
The empty list contains no elements, and the sum over nothing (the empty sum) is zero, so the base case is handled.
sumList [] = 0
Now, for the step case, what should the sum of all elements of the list x:xs be? Well, it should be the Urst element x, plus the sum of all the leftover elements xs. How do we compute the sum of xs? With sumList itself!
sumList (x:xs) = x + sumList xs Putting it all together,
So just like before, we have a function deUned in terms of itself. A recursive function recursing over a recursive data type!
Exercise 7
Submission required: Exercise 7 lengthList Exercise 8
(Hint: Consider which of these require a recursive solution, and which don’t.)
(Hint: What should the base case be?)
Submission required: Exercise 8 firstList Exercise 9
> append ‘d’ “worl” “world”
Submission required: Exercise 9 prepend, append Exercise 10
>swapLastTwo [1]
[1]
>swapLastTwo [1,2,3] [1,3,2]
(Hint: See the table of patterns above.)
Submission required: Exercise 10 swapFirstTwo, swapLastTwo Exercise 11
Submission required: Exercise 11 find
The pattern n:xs will match against the list, and the Urst element in the list will be assigned to n, which shadows, or overwrites, the variable n that is input to the function. As a result, this function always evaluates to True, and will not test if the n, referring to the Urst element of the list, is the same as the other n, the second input to the function. Haskell will give you a warning along the lines of This binding for n’ shadows the existing binding` if you try to do this.
Submit all your attempts at the above exercises via git.
Reinventing the wheel
Some of the functions we’ve written (sumList, lengthList) are so useful, they they’re already deUned in Haskell as sum and length respectively. We’ve had to name our functions different to avoid con`icts with the deUnition that already exists.
Extensions [COMP1100 Optional, COMP1130 Compulsory]
Recursion on multiple arguments
There’s no reason why we need to only recurse on one argument. Suppose we had a chessboard, and we wanted to colour in each square. How might we do it? Maybe by Ulling in the top row Urst, one square at a time, left to right. Then we jump down a row, and Ull it in, left to right. Then the next row, and so on.
We can do the same here in Haskell, and there’s two ways to do it. The Urst is to have a function row that just recurses along a single row, and then have a recursive function grid, that recurses along the column numbers, calling row for each column. Writing another function to help solve a small part of a bigger problem is a common programming technique, and we usually call the new functions helper functions, as they help us to solve the problem.
As an example, suppose we had some polynomial (like f(x) = x2 + 3x + 5) and we wanted to evaluate f(1) + f(2) + … + f(n). That’s a lot to do in one step, but by breaking up the problem into smaller parts, it becomes much easier to solve.
Here, we would call poly a helper function.
Another way is to do it is to have a function grid that takes two arguments, x and y. It counts along x until it reaches the end of the grid. x is then reset, and then y is increased by one. In this manner, we eventually can check every cell in the grid.
Extension 1
(The coordinates can be in a different order to the test cases shown, so long as they are all there.)
(Hint: Try using a helper function.)
Submission required for 1130 students: Extension 1 gridList Extension 2
Remember our fibonacci function? You might notice (depending on how you’ve implemented your function) that it’s quite slow for even reasonably sized numbers. Computing F100 seems like it should be easy for the computer to do, as it should only have to do 100 additions to get the last result. Yet, even to compute F40 takes a unreasonably long time.
What’s going on here? Think about this for a bit, chat with your neighbour, or ask your tutor.
(Hint: You may need a helper function to solve this problem. How many variables will this helper function need? What is changing after each recursive function call? Try computing some Ubonacci numbers by hand. What information do you need to compute the next number, and what information can be discarded? Chat to your neighbour, or ask your tutor.)
Submission required for 1130 students: Extension 2 fastFib
Don’t forget to submit all attempts at the exercises to git to recieve your participation marks.
This lab contains additional exercises for COMP1130 students. COMP1100 students are encouraged to attempt them once they have completed the compulsory exercises.
factorial :: Integer -> Integer factorial n
|n==0 =1
|otherwise = n * (factorial (n-1))
Those of you that have seen proof by induction before will notice the similar terminology, this is a very deliberate choice, as the concepts of recursion and induction are very heavily related.
Write the sumNumbers function, that computes the sum of all positive whole numbers up to and including n.
> sumNumbers 5 15
factorial -1
= (-1) * factorial (-2)
= (-1) * (-2) * factorial (-3)
= (-1) * (-2) * (-3) * factorial (-4) …
Fix the factorial and sumNumbers functions so that they return a sensible error message when given invalid input.
Unhelpful: error “whoops!”
Helpful: error “functionName: Negative inputs invalid”
Write a function called rangeSum that takes two integers, and returns the sum of all integers from the Urst to the second, inclusive.
>rangeSum 1 5 15
>rangeSum 3 6 18
Think carefully about which argument you will perform recursion over, and what the base and step cases should be.
I haven’t deUned what the function will do if the second argument is larger, like for the case of rangeSum 5 3. What do you think would be sensible behaviour here? Discuss with your neighbour or your tutor.
Write a function rangeSumEx that takes two integers, and returns the sum of all integers from the Urst to the second, inclusive of the Urst, but exclusive of the second.
>rangeSumEx 2 4 5
>rangeSumEx 3 6 12
Don’t forget to cover all cases, like if the second input is smaller than the Urst. Your code should never get trapped in an inUnite loop regardless of the input.
Write a function fibonacci that takes an Integer n and returns the n’th Fibonacci number.
What do you notice about trying to evaluate the Fibonacci function for inputs of size roughly 30?
The data type of String, an example of which is “hello”, is completely identical to [Char], which in this case would be [‘h’,’e’,’l’,’l’,’o’]. You should keep in mind that when you see String, you should think in your head “list of Char”, because that’s precisely what a String is.
>copy 5 ‘a’ “aaaaa”
copy :: Integer -> Char -> String copy n c
|n < 0 = error "copy: Negative input invalid" |n == 0 = []
|otherwise = c : copy (n-1) c
Write a function rangeList that takes two integers n and m, and returns a list of all numbers between n to m inclusive.
>rangeList 1 10 [1,2,3,4,5,6,7,8,9,10] >rangeList (-2) 2 [-2,-1,0,1,2]
Again, be careful to handle unexpected inputs. You code should NOT enter an inUnite loop for the input rangeList 5 1.
It’s common practice to denote elements of the list as x,y,z and the rest of the list as xs,ys,zs, but you could call the pattern variables anything. apple:banana is equally valid to the computer, if less readable to us humans. Stick to convention.
Pattern
Description
Example
[]
The (unique) empty list
[]
x:xs
Any non-empty list
[1], 2:[], [“cow”,”fox”]
[x] or x:[]
A singleton list
[1], [“cow”], [[]]
x:y:zs
A list with at least two elements
[1,2], [‘c’,’e’,’d’]
[x,y], x:[y], x:y:[]
A list with exactly two elements
[1,2], [[],[2]]
x:1:xs
A list with at least two elements, the second equal to 1
[3,1,3], [2,1]
x
Any list
[], [1], [“cow”], [[]]
_
Any list (and don’t assign a variable to the result)
[], [1], [“cow”], [[]]
sumList :: [Integer] -> Integer sumList list = case list of
[] ->0
x:xs -> x + sumList xs
Write a function lengthList that takes a list of Integer and returns how many numbers were in that list.
>lengthList [1,2,3,4] 4
>lengthList []
0
Write two functions. firstList takes a list of Integer, and returns the Urst element. lastList takes a list of Integer, and returns the last element.
>firstList [3,1,2,4] 3
>lastList [3,1,2,4] 4
Write two functions: prepend takes a Char, and a String, and adds the Char to the front of the String. append takes a Char and a String, and adds the Char to the end of the String
> prepend ‘h’ “ello” “hello”
Write two functions: swapFirstTwo swaps the Urst two integers in a list of integers, if they exist. swapLastTwo swaps the last two integers in a list of integers, if they exist.
>swapFirstTwo [1]
[1]
>swapFirstTwo [1,2,3] [2,1,3]
Write a function find, that takes an Integer x, and a list of Integer, and returns a Bool based on if x was in the list or not.
>find 3 [1,2,3,4,5] True
>find 9 [6,7,2] False
A common `aw is to attempt to use pattern matching to check for equality. For example, consider this function firstMatch, which takes a list, and an element, and checks if that element matches the Urst item in the list
firstMatch :: [Integer] -> Integer -> Bool firstMatch list n = case list of
n:xs -> True _ -> False
You should make sure you’ve completed all the above exercises Urst, before proceeding on to the extension exercises.
sumPoly :: Integer -> Integer sumPoly n
|n == 0 = 0
|otherwise = (poly n) + sumPoly (n-1)
where
poly :: Integer -> Integer poly x = x*x + 3*x + 5
Write a function called gridList that takes two Integer inputs, x and y, and returns a list of tuples representing the coordinates of each cell from (1,1) to (x,y).
>gridList 3 3 [(1,1),(2,1),(3,1),(1,2),(2,2),(3,2),(1,3),(2,3),(3,3)] >gridList 2 4 [(1,1),(2,1),(1,2),(2,2),(1,3),(2,3),(1,4),(2,4)] >gridList 4 2 [(1,1),(2,1),(3,1),(4,1),(1,2),(2,2),(3,2),(4,2)]
Once you think you’ve worked out why it’s slow, rewrite the Ubonacci function so it runs quicker. If you’ve done it correctly, you should be able to evaluate fastFib 100000 in under a second.
Updated: 06 Jun 2020
Responsible Opcer: Director, RSCS
Page Contact:
Course Convenor
Contact ANU
Copyright
Disclaimer
Privacy
Freedom of Information
+61 2 6125 5111
The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906