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

  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/2024s1/2024s1studentfiles/comp1100-2024s1-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 reflect the change: https://gitlab.cecs.anu.edu.au/uXXXXXXX/2024s1/2024s1studentfiles/comp1100-2024s1-lab05

  3. Clone your forked repository to your computer according to the instructions in the Week 2 Lab.

  4. Put your exercise solutions in the file Lab05.hs. This file is pre-filled with unfinished functions that match the exercises below.

This lab contains additional optional exercises. Students are encouraged to attempt them once they have completed the compulsory exercises to receive the participation marks for the lab.

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 \(n\), denoted \(n!\), is the product of all positive whole numbers less than or equal to \(n\).

\[n! = \begin{cases} 1 & n = 0\\ n \times (n-1)! & \text{otherwise} \end{cases}\]

We define \(0!=1\) by convention.

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 \(0! = 1\), and the step case is defining \(n! = n \times (n-1)!\) for all numbers larger than zero.

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 \(F_n\) is as follows: \(0,1,1,2,3,5,8,13,21,\ldots\) The pattern that the sequence follows is that the first two terms are defined to be zero and one respectively, \((F_0 = 0, F_1 = 1)\) and then each successive term is the sum of the previous two.

Write a function fibonacci that takes an Integer n and returns the nth Fibonacci number.

As a test, verify that \(F_{30} = 832040\).

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 of Integer and returns the first element,
  • lastList takes a list of Integer, 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 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"

> 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) are so useful that they they’re already defined in Haskell as sum and length respectively. We’ve had to name our functions differently to avoid conflicts with the definition that already exists.

You should make sure you’ve completed all the above exercises first, before proceeding on to the extension exercises.

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 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 \(f(x) = x^2 + 3x + 5\) and we wanted to evaluate \(f(1) + f(2) + \ldots + 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.

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.)

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 \(F_{100}\) 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 \(F_{40}\) takes a unreasonably long time. What’s going on here? Think about this for a bit, chat with your neighbour, or ask your tutor.

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.)

Submission required for 1130 students: Extension 2 fastFib

bars search times arrow-up