Lab Exercises Week 3

Basic Control Structures & Data Structures

• More About XEmacs
• Exercise 1
• Exercise 2
• Additional Exercise

Lab1 covered some basic features of XEmacs, such as file loading and saving. These features were activated using the mouse (ie, using point-and-click¹ operations). The disadvantage of using a mouse is that it requires you to take one hand from the keyboard, move it to the mouse, and back to the keyboard to continue typing. This can become annoying when you become a proficient computer user.

Therefore, any halfway decent program can also be operated using the keyboard only - without touching the mouse (drawing programs and the like excepted). To allow the computer to distinguish between keystrokes meant to input text and those that are used to control the program (i.e., those replacing mouse operations), there are a couple of modifier keys on the keyboard. The most important of them is the control key (the one labelled Ctrl). In the following, when I write C-x, I mean pressing the control key simultaneously with the key labelled x. Moreover, I write sequences of keystrokes as C-x b or C-x C-b. Note that these two sequences are different. The former specifies to hold down the control key only while pressing x, whereas the latter means to press down the control key while pressing x and while pressing b.

XEmacs allows all operations to be performed by keyboard only - in fact, many of the advanced features are only available via the keyboard. Therefore, let us have a look at some basic XEmacs keyboard wizardry, which you will find useful when writing Haskell programs. Start up xemacs by typing xemacs & into an terminal window (and don't forget to leave the mouse cursor over the XEmacs window while typing into XEmacs).

• Now, let's load last week's lab exercise without using the mouse. Type C-x C-f (so, control is used with both x and f); then, the cursor will move to the minibuffer (that is, the line at the very bottom of the XEmacs window) and you can enter the file name Lab02.hs (which you should have used last week).
• When last weeks solution appears, use C-c C-l to run GHCi within XEmacs and to load Lab02.hs into GHCi in one go.
• You will notice that the input area of XEmacs suddenly was split into two halves. Your program is in the upper half and GHCi in the lower half. (This will be a familiar sight from the lectures.) We call each of these two halves an XEmacs window (no to be confused with the graphical windows in which programs like terminal windows and XEmacs itself run).
• Use C-x o to jump from one window into the other.
• When in the window containing Lab02.hs, try C-x 1. It will remove the other window (the one displaying GHCi). By typing C-c C-l once again, you can make GHCi appear again (and actually reload you code into GHCi).
• If your Haskell program has an error, the error message will be displayed in the window containing GHCi and the cursor will automatically jump into the line of which GHCi claims that it contains the error (this may not be entirely accurate in case of complicated errors, but gives you an idea of where to start searching for the error).

Here is a summary of the commands. I recommend compiling a list of XEmacs commands as you learn them, for easy reference when you forget something. (There will be other useful commands in coming lab exercises.)

C-x C-f

Load a file or create new file with given name.

C-x C-s

Save current buffer.

C-x 0

Remove the current window (if there are more than two windows displayed).

C-x 1

Remove all but current window.

C-x o

Move cursor to the other window.

C-c C-l

Load the Haskell program from the current buffer into GHCi. This works only in buffers containing Haskell code whose file name ends in .hs.

Observe how all commands manipulating buffers and windows start with C-x and the second key in the key sequence was chosen to be mnemonic.

As both the XEmacs and GHCi installation on CSE machines is very new, you may experience problems when attempting to use C-c C-l. In this case, ask your tutor for help.

Start a new file called Lab03.hs into which you add your solutions to the this week's Haskell exercises. 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. (Remember that comment lines start with --.) Then, introduce the new module with the two lines

module Lab03
where

Your function definitions follow this module header.

When implementing the functions outlined below, make sure that you follow the Five Steps to Designing and Implementing a Function from the lecture. Your tutor will check that you added a description and examples to the comment preceding each function and that you have tested it properly. You will only get lab marks for functions that a properly implemented using the five steps.

Positive Number: isPositive

Implement a function isPositive :: Int -> Bool that returns True if the input value is greater than zero, False otherwise. The use of the funtion would look as follows:

Lab03> isPositive 3
True
Lab03> isPositive (-3)
False

Note the parenthesis around the literal -3. They are necessary to avoid a syntax error.

Sort three numbers: sort3

Write a function sort3 that has type

sort3 :: Int -> Int -> Int -> (Int, Int, Int)

I.e., it gets three integer arguments and also returns three integer values. In fact, it should return exactly the same values, but ordered such that in the resulting triple, the smallest number is first and the greatest last. The following examplifies the use of the function:

Lab03> sort3 5 7 8
(5,7,8)
Lab03> sort3 7 5 8
(5,7,8)
Lab03> sort3 7 8 5
(5,7,8)
Lab03> sort3 8 7 5
(5,7,8)
Lab03> sort3 8 5 7
(5,7,8)
Lab03> sort3 5 8 7
(5,7,8)

Range of numbers: rangeWithInc

Write a function rangeWithInc that gets an interval - i.e., a pair of numbers specifying the interval's start and end value - together with an increment value as arguments. It yields all numbers in the interval that can be obtained by adding the increment onto the start value. The function has type

type Interval = (Int, Int)

rangeWithInc :: Interval -> Int -> [Int]

and it behaves as follows:

Lab03> rangeWithInc (1, 10) 1
[1,2,3,4,5,6,7,8,9,10]
Lab03> rangeWithInc (1, 10) 3
[1,4,7,10]
Lab03> rangeWithInc (8, 20) 2
[8,10,12,14,16,18,20]

Hint: Use the [x, y..z] operation.

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

"Sort three numbers" revisited

What is the minimal number of comparisons needed to implement sort3? Less than three comparisons will generally not be sufficient, but in fact it is possible to restrict the implementation to not using more than three comparisons. Write a second version of sort3 - call it sort3' (i.e., a prime character added after the previous name of the function) - but this time, the function is not allowed to use more than three comparisons to compute the result.

Hints: You will have to use a where clause. In fact, there are two possible solutions - one of them makes use of sort2 from this week's tutorial exercises (both solutions are ok).

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

The following is an additional exercise 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.

Write a function bothTrue:: Bool -> Bool -> Bool that returns True if and only if both its inputs are True.

      Lab03> bothTrue True False
      False
      Lab03> bothTrue True True
      True
      Lab03> bothTrue False False
      False
      Lab03> bothTrue False True
      False
      Lab03> bothTrue (6 < 100) ('a' < 'b')
      True
      Lab03> bothTrue ("Haskell" == "uncool") (4*5 == 20)
      False

Can you do this without using pattern matching or the && function?

Footnotes

¹Hackers² sometimes teasingly call these interfaces point-and-drool interfaces.

²I am using the term hacker in its original sense, where it describes a computer expert who enjoys exploring the details of programmable systems. This is in contrast to the misuse in main stream media who use the term wrongly for a person breaking into computer systems with a malicious intention. The correct term for such a person is cracker.³

³These are recursive footnotes³ and if you find them funny, you have already understood the essence of recursion. (If you don't find them funny, it doesn't mean that you didn't understand recursion, but only that you don't have such a twisted sense of humour as I have ;-)