COMP1011 Exercises for Week 06
Computing 1A 05s2 Last updated Fri 26 Aug 2005 22:01
Mail cs1011@cse.unsw.edu.au

# Lab Exercises Week 6

## Patterns of Recursion & Higher-Order Functions

### Ex 1:

Start a new file called `Lab06.hs` into which you add your solutions to the this week's Haskell exercises. As in earlier weeks, before beginning with the exercises, don't forget to add comments at the beginning of this file, which describe the purpose of this Haskell module and who wrote it. Also, follow the Five Steps when developing the functions and start by writing a proper description and examples.

Like last week, when you have trouble with a function that behaves in the wrong way, consider how to use `trace` to find the bug in your implementation.

#### Sieve of Eratosthenes

The Greek mathematician Eratosthenes (276 BC - 194 BC) invented an algorithm to compute all prime numbers up to a given maximum fairly efficiently. The algorithm computes the prime numbers smaller than N by starting with the set of all numbers from 2 up to N - 1. It then repeats the following steps until the set is empty:

• It removes the smallest number from the set; let's call it x.
• The number x is guaranteed to be a prime number, and so, we put it into the list of results.
• All multiples of x (i.e., x, 2*x, 3*x, etc.) are removed from the current set of numbers. In fact, only the multiples of x smaller than the square root of N need to be removed.

Implement a function `sieve :: Int -> [Int]` that implements the Sieve of Eratosthenes and takes N as its argument. It might be used as follows:

```Lab05> sieve 100
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]```

Note that the implementation of this algorithm requires both generative and nested recursion. In particular, you are encouraged to implement the two helper functions `sieve' :: [Int] -> [Int]` and `removeMultiples :: Int -> [Int] -> [Int]`. The idea is that `sieve'` takes the current set of numbers as its argument and implements the repetition of the three main steps of the Sieve of Eratosthenes. Moreover, `removeMultiples` removes all multiples of its first argument from its second. To be able to stop removing multiples greater than the square root of N, define both `sieve'` and `removeMultiples` as local functions to `sieve`; i.e., within a `where` clause.

A quick method to check whether a number k is a multiple of x is to determine whether the reminder of the integer division of k/x is zero; i.e., in Haskell, `k` is a multiple of `x` iff ```k `mod` x == 0```.

When you have completed the above exercise show it to your tutor for this week's core mark.

### Ex 2:

#### Updating the movie database: `rent` - revisited

Like last week, assume the following type definition and miniature movie database from the lecture:

```type MovieList = [(String, Bool)]  -- title, rented

movies = [("The Matrix"  , False),
("Strange Days", True ),

This time, implement the function

`rent :: MovieList -> String -> MovieList`

using the higher-order function `map`, such that it updates the movie database and raises an error if the title is already rented out. (To keep matters simpler, you don't need to raise an error if the movie is not in the database.)

```Lab06> rent movies "Blade Runner"