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 ),
          ("Blade Runner", False)]

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" 
[("The Matrix",False),("Strange Days",True),("Blade Runner",True)]
Lab06> rent movies "Strange Days" 
<probably some garbage here>
Program error: rent: movie already rented

Lab06> rent movies "Final Fantasy" 
[("The Matrix",False),("Strange Days",True),("Blade Runner",False)]

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