Lab Exercises Week 5

More Recursion & Lists

Unix Literacy

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

1. Book a terminal.
2. Copy a file to floppy disk, and from a floppy disk; alternatively, use a USB memory stick (many lab machines have an accessible USB slot).
3. Use ssh (maybe from putty) to run a unix session from home.
4. Use sftp/scp to transfer files to/from uni over the internet.

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.

Emacs Literacy

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

This key sequence brings you into Emacs' documentation subsystem. It contains documentation to Emacs and many other Unix programs - in particular, those from the GNU project. You can leave the documentation subsystem by pressing q.

C-h a

This invokes the keyword search facilities. You can input a keyword in the minibuffer and get a list of functions matching this keyword.

C-h k

You will be ask to input any key sequence, and then, Emacs will tell you which operation is invoked with that sequence. For example, C-h k C-h k (i.e., typing C-h k twice) will tell you what C-h k does.

Ex 1:

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.

Test for the superlist property: 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 a list in two: 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.

Ex 2:

Updating the movie database: 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.

Additional Exercises

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

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

Quicksort

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.