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 first recursive data type, lists, that can pack many instances of a type together. We will write recursive functions over integers and lists.
Don’t forget to submit all attempts at the exercises to git to receive your participation marks.
Table of Contents
Pre-Lab Checklist
- You should have finished 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
-
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/2024s2/2024s2studentfiles/comp1100-2024s2-lab05
-
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/2024s2/2024s2studentfiles/comp1100-2024s2-lab05 -
Clone your forked repository to your computer according to the instructions in the Week 2 Lab.
-
Put your exercise solutions in the file
Lab05.hs
. This file is pre-filled with unfinished functions that match the exercises below.
Recursion
Recursion is a concept borrowed from mathematics where a function is defined 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
We define
Note that the factorial function is defined in terms of itself, which makes it a recursive function.
Recursively defined mathematical functions are very easily translated into Haskell. The definition 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.
factorial :: Integer -> Integer
factorial n
| n == 0 = 1
| otherwise = n * (factorial (n-1))
Now how factorial
appears in the definition of factorial
, just as
it does in the original definition above.
Almost all recursive functions follow a similar pattern, by defining the function for the “first”, or the “simplest” input, called the base case, and then defining the function for all other inputs recursively. We call this the step case.
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.
For the case of the factorial function, the base case is defining
For this lab, put all your answers in the file Lab05.hs
provided.
Exercise 1
Write the sumNumbers
function, which computes the sum of all
positive whole numbers up to and including n
.
> sumNumbers 5
15
(Hint: Think about what the value of sumNumbers 0
should be.)
Submission required: Exercise 1 sumNumbers
Undefined Behaviour and Infinite Loops
The factorial function is only defined 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.
factorial -1
= (-1) * factorial (-2)
= (-1) * (-2) * factorial (-3)
= (-1) * (-2) * (-3) * factorial (-4)
...
It’s pretty clear that this code isn’t going to terminate. (If you did run it and it’s trapped in an infinite loop, type “Ctrl-C” (hold down the “Ctrl” key and “C” keys together 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
Fix the factorial
and sumNumbers
functions so that they return a
sensible error message when given invalid input.
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.
Unhelpful: error "whoops!"
Helpful: error "functionName: Negative inputs invalid"
Submission required: Exercise 2 Invalid Input
Exercise 3
Write a function called rangeSum
that takes two integers,
and returns the sum of all integers from the first 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 defined 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.
Submission required: Exercise 3 rangeSum
Exercise 4
Write a function rangeSumEx
that takes two integers, and
returns the sum of all integers from the first to the second,
inclusive of the first, 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 first. Your code should never get trapped in an infinite loop regardless of the input.
Submission required: Exercise 4 rangeSumEx
Exercise 5
The Fibonacci sequence
Write a function fibonacci
that takes an Integer n
and returns the
n
th Fibonacci number.
As a test, verify that
What do you notice about trying to evaluate the Fibonacci function for inputs of size roughly 30?
Submission required: Exercise 5 fibonacci
Lists
Lists are very useful for storing a sequence of elements, all of the same type.
An informal definition of lists in Haskell looks like this:
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 “list constructor”). We sometimes say a
is “cons-ed” onto
the list [a]
.
Note that the definition of list contains itself, just like the definition 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]]]
.
The data type String
, a value of which is "hello"
, is defined as
“list of Char
” [Char]
. The value "hello"
is actually just
“syntactic sugar” for the value ['h','e','l','l','o']
— they are
one and the same thing! You should keep in mind that when you see
String
, you should think in your head “list of Char
” [Char]
,
because that’s precisely what a String
is.
Examples of Lists
If we want the list containing 1, then 2, then 3, we could write that as:
1:(2:(3:[]))
But that is rather verbose, so Haskell has a nice shorthand way (more
syntactic sugar) 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 the same thing.
In fact, the brackets above are unnecessary since the operator :
is
right-associative: 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 first 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.
>copy 5 'a'
"aaaaa"
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,
copy :: Integer -> Char -> String
copy n c
| n < 0 = error "copy: Negative input invalid"
| n == 0 = []
| otherwise = c : copy (n-1) c
Exercise 6
Write a function rangeList
that takes two integers n
and m
, and
returns a list of all numbers from n
to m
(inclusively).
>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 infinite loop for the input rangeList 5 1
.
Submission required: Exercise 6 rangeList
List Patterns
Sometimes, rather than constructing new lists, we want 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 its contents.
It’s common practice to denote elements of a list as x
, y
, z
,
etc., and the rest of a list as xs
, ys
, zs
, etc., but you can
call the pattern variables anything. apple:banana
is equally valid
to the computer, if less readable to us humans. Stick to convention.
Here is a list of useful list patterns:
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"] , [[]] |
Functions on Lists
Now that we know how to match against list patterns, let’s write some
functions over lists. Lists are a recursively defined 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
definition, 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 “list of
Integer
” [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 first 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,
sumList :: [Integer] -> Integer
sumList list = case list of
[] -> 0
x:xs -> x + sumList xs
So just like before, we have a function defined in terms of itself. A recursive function recursing over a recursive data type!
Exercise 7
Write a function lengthList
that takes a list of Integer
and
returns how many numbers are in that list.
>lengthList [1,2,3,4]
4
>lengthList []
0
Submission required: Exercise 7 lengthList
Exercise 8
Write two functions:
firstList
takes a list ofInteger
and returns the first element,lastList
takes a list ofInteger
, and returns the last element.
>firstList [3,1,2,4]
3
>lastList [3,1,2,4]
4
(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
Write two functions:
prepend
takes aChar
and aString
, and adds theChar
to the front of theString
,append
takes aChar
and aString
and adds theChar
to the end of theString
.
> prepend 'h' "ello"
"hello"
> append 'd' "worl"
"world"
Submission required: Exercise 9 prepend, append
Exercise 10
Write two functions:
swapFirstTwo
swaps the first 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]
>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
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
Submission required: Exercise 11 find
A common flaw 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
first item in the list:
firstMatch :: [Integer] -> Integer -> Bool
firstMatch list n = case list of
n:xs -> True
_ -> False
The pattern n:xs
will match against the list, and the first element
in the list will be bound to n
, which shadows, or hides,
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 first 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
, find
) are so
useful that they they’re already defined in Haskell, as sum
,
length
, and elem
respectively. We’ve had to name our functions differently to
avoid conflicts with the definition that already exists.
If you used these existing functions for your solutions, well done on finding them!
But it would be a valuable exercise for you to try to implement these functions
from scratch without relying on the Prelude.
You should make sure you’ve completed all the above exercises first, before proceeding on to the extension exercises.
Extensions
[Optional, not required for participation marks]
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 filling in the top row first, one square at a time, left to right. Then we jump down a row, and fill it in, left to right. Then the next row, and so on.
There’s two ways to do this. The first 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
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
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
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)]
(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.)
Optional Submission: 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
Once you think you’ve worked out why it’s slow, rewrite the Fibonacci
function so it runs quicker. If you’ve done it correctly, you should
be able to evaluate fastFib 100000
in under a second.
(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 Fibonacci 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.)
Optional Submission: Extension 2 fastFib