1       (20 marks)

In this question you are asked to define types, as well as values.  Each type, Name, is given a default implementation: type  Name  =  REPLACE_THIS_TYPE. You may change the        keyword type to either newtype or data if appropriate, and you should replace                REPLACE_THIS_TYPE, by a suitable type expression. You may derive any type classes, such as Show, that will be useful.

Marks will be mostly given for how well the type protects the programmer from mistakes,

for its utility to the programmer, and also partly for the run-time efficiency of the type.

This question relates to preparing a play list of songs for a radio programme.

A programme consists of segments. The total time of songs scheduled should not exceed

the time available in a segment.

The time required for a song includes the time to introduce it.

All times are given in whole numbers of seconds.

No song may be repeated in a programme. Songs are identified by an Integer ID, which is

guaranteed to be different for different songs, even if the titles are the same.

A record is represented by:

data  Song  =  Song  {ident  ::  Int,  title  ::  String,  duration  ::  Int} deriving  (Show)

(i)     [3 marks]

Instantiate Song as a member of class  Eq.

instance  Eq  Song  where

(==)  =  undefined

(ii)    [7 marks]     Define suitable types to represent segments and programs.  Programmes are  collection of segments, and segments have durations (in whole numbers of seconds) as well as a collection of songs to be played during the segment.

type  Programme  =  REPLACE_THIS_TYPE

type  Segment  =  REPLACE_THIS_TYPE

(iii)   [10 marks]     Define functions to determine if songs, segments and programmes are valid:

■  a song is valid if its title is not empty, and its duration is positive,

■  a segment is valid if the total time taken by the songs fits into the duration of the segment and all the songs are valid.

■  a programme is valid if all its segments are valid, and no song is repeated.

validSong  ::  Song  ->  Bool

validSegment  ::  Segment  ->  Bool

validProgramme  ::  Programme  ->  Bool

validSong  =  undefined

validSegment  =  undefined

validProgramme  =  undefined

2       (15 marks)

The Society Of Fast Food Fanciers wants to keep a database of food suppliers, with a

recommendation for each food type sold by those suppliers.

A recommendation is captured by the data type Recommendation:

data  Recommendation  =  Bad  |  Poor  |  Good  |  Excellent deriving  (Eq,  Show)

They are considering two different representations, generic in the type of outlet names and

food names.

The first keeps a list of triples:

newtype  RecL  outlet  food  =  RecL  [((outlet,  food),  Recommendation)] For example, assumming sutable instantiations of shop and food:

RecL  [((RCH,  Pizza),  Poor),  ((PZA,  Burrito),  Good)]

The second stores the recommendations in a function:

newtype  RecF  outlet  food  =  RecF  ((outlet,  food)  ->  Maybe  Recommendation)

For example:

RecF  (\  otfd  ->  case  otfd  of

(RCH,  Pizza)      ->  Just  Poor

(PZA,  Burrito)  ->  Just  Good

_                           ->  Nothing)

For each of the tasks 2(i), 2(ii) and 2(iii) below, give two solutions, one using each type.

(i)     [2 marks]     Give values to represent an empty database:

emptyL  ::  RecL  outlet  food

emptyF  ::  RecF  outlet  food

emptyL  =  undefined

emptyF  =  undefined

(ii)    [7 marks]      Give functions to enter a new recommendation.  If a recommendation for the

given food at the given outlet already exists, then the new recommendation replaces the old

one.

enterL  ::  (Eq  outlet,  Eq  food)  =>

outlet  ->  food  ->  Recommendation  ->  RecL  outlet  food  ->  RecL  outlet  food enterF  ::  (Eq  outlet,  Eq  food)  =>

outlet  ->  food  ->  Recommendation  ->  RecF  outlet  food  ->  RecF  outlet  food

enterL  =  undefined

enterF  =  undefined

(iii)   [6 marks]      Give functions to report a recommendation, if there is one, and Nothing

otherwise:

reportL  ::  (Eq  outlet,  Eq  food)  =>

outlet  ->  food  ->  RecL  outlet  food  ->  Maybe  Recommendation reportF  ::  (Eq  outlet,  Eq  food)  =>

outlet  ->  food  ->  RecF  outlet  food  ->  Maybe  Recommendation

reportL  =  undefined

reportF  =  undefined

3       (10 marks)

Recall the definition of the ProofLayout type constructor:

infixr  0  :=:  - -  the  fixity  and priority  of  the  operator

data  ProofLayout  a  =  QED  |  a  :=:  ProofLayout  a  deriving  Show Consider the Prelude functions:

length  ::  [a]  ->  Int

length  []          =  0                           - -  length . 0

length  (_ :xs)  =  1  +  length  xs  - -  length . 1

(++)  ::  [a]  ->  [a]  ->  [a] []         ++  ys  =  ys

(x:xs)  ++  ys  =  x  :  (xs  ++  ys)

- -  (++) . 0

- -  (++) . 1

Prove that length distributes over concatenation:

forall  xs,  ys  ::  [a]  {length  (xs  ++  ys)  ==  length  xs  +  length  ys}

You may assume

0  +  n  ==  n  - -  (+) .unit