UserPreferences
2005 1711
Junior Syllabus
Tute07

Tutorial Week 7

Bring a printout of this page with you to your tutorial.

Any *starred questions are for your own practice at home and won't be covered in the tutorial unless you have questions for your tutor about them.

Presentation topic

Don't forget to read the [WWW]presentation info page

Explain the efficient exponentiation algorithm described in lab question 3.

Exercises

Q1. polymorphic type signatures

Q2. Pattern matching

Write one line functions using pattern matching to do the following:

  1. Return the third element of a 4 element tuple

  2. Return True if the 2nd element of a list of Ints is 42

  3. Return True if the input list has exactly 3 elements

  4. Return True if the input list has at least 3 elements

  5. Return True if the input list is non-empty

Q3. Defining algebraic types

Q4. Using algebraic types

Below are three functions which use algebraic types. Your tutor will do the first one in the tute, you pick one of the others for the lab (whichever of the remaining two you think will be most helpful for you to do), and save the remaining one to do at home for practise if you need more help with algebraic types.

Fraction
This question refers to a type Fraction defined as: 
data Fraction = Ratio Integer Integer |
                Whole Integer         |
                Mixed Integer Integer Integer
  deriving (Show)
(Ratio 3 4) represents 3/4 (ie 0.75 in decimal)

(Whole 42) represents the whole number 42 (ie 42.0 in decimal)

(Mixed 4 3 5) represents 4 and 3/5 (ie 4.6). Note that (Mixed 4 6 5) is also legal (although ugly) and represents 5.2.

Write functions to add, subtract, and (if you have time) subtract and multiply two Fractions. Have your functions simplify their outputs (ie the numerator and demonimator in Mixed and Ratio outputs are to have no factors in common, and if the denominator is 1 then return a Whole output.)

Here are some examples of how your functions are to behave: 

Week07> add (Whole 4) (Ratio 5 3)
Ratio 17 3
Week07> add (Ratio 1 6) (Ratio 1 2)
Ratio 2 3
Week07> minus  (Ratio 2 3) (Ratio 1 6)
Ratio 1 2
Week07> multiply (Mixed 6 1 5) (Whole 6)
Ratio 186 5
Week07> divide (Ratio 5 64) (Ratio 15 8)
Ratio 1 24
Week07> (divide (Whole 1) (Whole 3628800)) `multiply` (Whole 3628800)
Whole 1
Brain teaser: Why didn't we derive Eq for Fraction?

Lock
(from a past prac exam)

Note: Widdershins means anti-clockwise.

Consider the lock on a safe. Suppose it consists of a dial numbered from 0 to 35. You operate it by rotating the dial clockwise or widdershins certain amounts. An output is generated every time the dial changes direction, and when it finally stops. The lock opens if the correct sequence of outputs is generated.

For example, suppose that the dial is initially pointing to 0. We could generate the sequence 6,4,5 by rotating 6 steps in a widdershins direction, then 2 steps in a clockwise direction, then 1 step widdershins. Or we could have generated the same sequence rotated 30 steps clockwise, 34 steps widdershins, 71 steps clockwise.

We can define a rotation type as follows: 

data Rotation = Clockwise Int | Widdershins Int
   deriving (Show)
Write a function lock :: [Rotation] -> [Int] which returns the output sequence generated by a list of rotations. You may assume that the list of rotations is not empty, and that the dial is initially pointing to 0.

For example: 

Week07> lock [(Widdershins 6),(Clockwise 2),(Widdershins 1)] 
[6, 4, 5] 
Week07> lock [(Widdershins 1),(Widdershins 1),(Widdershins 1)] 
[3] 
Week07> lock [(Widdershins 100)] 
[28] 
Week07> lock [(Clockwise 30),(Widdershins 34),(Clockwise 35)] 
[6, 4, 5] 
Week07> lock [(Clockwise 4),(Widdershins 1)] 
[32, 33] 
Week07> lock [(Clockwise 4),(Widdershins 1),(Widdershins 3), (Clockwise 20), (Widdershins 6), (Clockwise 5), (Clockwise 5), (Widdershins 8)] [32, 0, 16, 22, 12, 20]

Brainteaser: Why wouldn't it make sense to derive Eq for the type Rotation in this situation?

Robot
(past prac exam question)

Suppose you are given the following types: 

data DirectionType = North | South | East | West
   deriving (Eq)

data MoveType = Face DirectionType | Forward Float | Backwards Float
   deriving (Eq)
We have a robot which responds to orders of MoveType. For example when told: (Face North) the robot turns so it is facing North. When told: (Forward 4.5) the robot moves forward 4.5m.

Forward means move in the direction it is currently facing. Backwards means move in the opposite direction to the direction it is currently facing. This does not alter the way it is facing.

So, the instructions: 

[(Face East), (Forward 3), (Backwards 2.1)]
would result in the robot moving to a point 0.9m East of its starting point.

Write a function distance :: [MoveType] -> Float which, given a sequence of moves, computes the distance between the robot's starting point and where it stops.

You may assume that the robot is initially facing North.

For example: 

Week07> distance [(Face East), (Forward 3), (Backwards 2.1)]
0.9
Week07> distance [(Forward 2), (Forward 3)]
5.0
Week07> distance []
0.0
Week07> distance [(Forward 3), (Face South), (Forward 4)]
1.0
Week07> distance [(Face South), (Forward 3), (Face West), (Backwards 4)]
5.0
Week07> distance [(Face South), (Face East), (Forward 1), (Face South), (Forward 1), (Face West), (Forward 1), (Face North), (Forward 1)]
0.0
Week07> distance [(Face South), (Forward 5), (Face East), (Forward 10), (Backwards 1), (Face West), (Forward 1), (Face North), (Forward 16), (Face West)]
13.6015

Recall that the hypotenuse of a right angled triangle is given by h2 = a2 + b2

Q5. Task2

Discuss as required and start planning the group work to crack the Black network (starts on the weekend once yellow is closed)

Q6. Task1

Has been automarked and is now with your tutors for style marking. 15 sample student assignments and their style marks available in the [WWW]Style-Example forum. The [WWW]files we used for automarking are now available. Fifteen of the tests are listed at the end of the ReaderABCD module, the 16th test is just on (a tweaked version of) "SpookyHouse".

Home*. Pattern matching

Write your own version of the built in function unzip :: [(a,b)] -> ([a],[b]). Experiment with unzip to deduce what it does.

PS Why do you think it is called unzip?