COMP1011 Exercises for Week 06 | |
---|---|
Computing 1A 05s2 |
Last updated
Fri 26 Aug 2005 22:01
Mail cs1011@cse.unsw.edu.au |
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.
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:
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.
rent
- revisitedLike 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.