COMP1011 Exercises for Week 05 | |
---|---|
Computing 1A 05s2 |
Last updated
Sun 21 Aug 2005 20:50
Mail cs1011@cse.unsw.edu.au |
Do the exercises in this section before or after your lab. There is not enough time in the lab for this plus solving the Haskell exercises.
If you do your assignment work at home or prepare for the lab at home,
you will need to transfer files between your home machine and uni. You
may even want to log into uni remotely from your home machine - eg, to
run give
. So, make sure that you can do the following
tasks (rather than trying it for the first time 1 hour before the
assignment deadline):
Information on how to do these tasks is generally available from the CSE Help & Documentation page. In particular, the FAQ has a lot of good tips. If you don't manage to find out how to do the above tasks on your own, ask your tutor for help.
When you log into uni from home, you can still use XEmacs - even via a purely textual ssh connection. If you start Emacs with
xemacs -nw
(instead of xemacs &
) it will not open a new window, but
run in place of the shell from which you are starting it. (The switch
-nw
stands for "no window".) The lack of a window will,
however, mean that you cannot use the mouse to access the pull down
menus. There is a workaround,
but the easiest solution is to get used to the key combinations for
loading and saving files and so on. (Using the key combinations instead
of the mouse will also enable you to work much faster, even when Emacs
is running in a window.)
When you run Emacs in a shell, the key combination C-z
is
very useful. It suspends Emacs and gets you back to the shell
prompt. You can now execute shell commands like ls
and
cd
. To get back to Emacs type the command fg
in the shell. You will be right were you suspended Emacs. In this way,
you can switch back and forth between Emacs and the shell without
loosing the current state of work in Emacs.
Note: When Emacs runs in an extra window,
C-z
iconifies this window.
When you forgot an Emacs command or you want to learn new ones, Emacs
can help you finding the right information. Try the following commands
(they are also available from the Help
menu entry):
C-h i
q
.
C-h a
C-h k
C-h k C-h k
(i.e., typing C-h k
twice) will
tell you what C-h k
does.
Start a new file called Lab05.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.
This 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.
superlist
Write a function superlist
that checks whether each element
of a list of integers is also contained in a second list of integers:
Lab05> [3,2,1] `superlist` [1..2] True Lab05> [3,1] `superlist` [1..2] False Lab05> [3,1] `superlist` [] True
You can use the function elem
from the lecture, which is in
fact already predefined in Haskell - you can just use it without
defining it yourself. Remember that function names in backquotes can be
used as infix operators.
split
Implement a function that given an integer - called the median - and a list of integers, returns two lists: one list containing all elements smaller or equal the median and the second list containing those elements bigger than the median:
Lab05> split 6 [5,3,6,8,9,3,2,1,4,7,8,9,7] ([5,3,6,3,2,1,4],[8,9,7,8,9,7]) Lab05> split 9 [1..10] ([1,2,3,4,5,6,7,8,9],[10])
When you have completed the above exercises show them to your tutor for this week's core mark.
rent
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)]
Write a function
rent :: MovieList -> String -> MovieList
that updates the movie database and raises an error if the title is not in the database or is already rented out.
Lab05> rent movies "Blade Runner" [("The Matrix",False),("Strange Days",True),("Blade Runner",True)] Lab05> rent movies "Strange Days" <probably some garbage here> Program error: rent: movie already rented Lab05> rent movies "Final Fantasy" <probably some garbage here> Program error: rent: unknown movie
When you have completed the above exercise show them to your tutor for this week's advanced mark.
The following are an additional exercises to help you getting practice in programming. It is not part of the lab mark, but it should help you understand some of the material covered in the lecture. (This week's additional exercises are not easy.)
superlist
Can you implement superlist
such that it works for lists of
integers and lists of characters (and other types also)?
(Hint: This requires the use of a type class.) Note that the
command :t
in GHCi gives you the type of a function or
expression. For example,
:t elem
prints the type of elem
.
The famous computer scientist C. A. R. Hoare
invented a sorting algorithm called Quicksort. You can
implement it using the function split
of this week's lab.
The implementation recursively traverses the input list and calls
split
once in each recursive step. Can you figure out how
to do it and implement a function qsort
? To make it a
little simpler, assume that there are no duplicates in the input list.