DAY: 2017-10-28 | TIME: 14:00–18:00 | PLACE: SB Multisal |
Responsible: Aids: Grade: |
David Sands 0737207663 [Will visit the exam rooms between 15.00 and 15.30] An English (or English-Swedish, or English-X) dictionary
Completing Part I gives a 3 or a G; |
Part I (7 small assignments)
|
Part II (2 larger assignments)
|
Please read the following guidelines carefully: |
Part I
You have to complete 5 out of the following 7 assignments to get a pass on the exam.
Given the following function
q1 :: [Int] -> Int
q1 [] = 0
q1 [x] = x
q1 (x:_:xs) = max x (q1 xs)
what would the following expression give in ghci?
q1 (map abs [-1,-6,-5,7])
In this question you should assume that you have a function rainfall
which computes the rainfall in Gothenburg for a given week (where weeks are numbered from 1 and upwards)
type WeekNumber = Int
rainfall :: WeekNumber -> Double -- assume this function exists
A week is considered to be “dry” if the rainfall in that week is less than 5.
Complete the definition of the following function:
dryWeeks :: WeekNumber -> Int
dryWeeks n | n < 1 = 0
-- (complete this definition)
such that dryWeeks n
(when n > 0
) gives the number of dry weeks in the range 1 up to n.
Your solution must be recursive. Solutions that do not use recursion will be considered incorrect. Solutions which always return the value 0 (whether intended as a joke or otherwise) will also be considered incorrect!
In this question you should define a data type to represent a bus ticket of a certain kind described below.
A bus ticket is either a single ticket (a ticket valid for a certain number of minutes) or a period ticket (a ticket that lasts a number of whole days). A single ticket is marked with the date and time when it expires. A period ticket is marked with the date when it expires.
You should use the types Date
and Time
given below (although the details of their definitions are not important for this question):
type Year = Int
type Month = Int
type Day = Int
type Hour = Int
type Minute = Int
data Date = Date Year Month Day
data Time = Time Hour Minute
Your task is (only) to complete the following definition:
data BusTicket = ...
Note: you do not have to define any functions, or write any deriving ...
.
The following data type represents arithmetic expressions with multiplication, addition, subtraction and a variable X:
data Expr = X | Num Int | BinOp Op Expr Expr
deriving (Eq,Show)
data Op = Add | Mul | Subtract
deriving (Eq,Show)
Although this data type can represent subtraction, it is not really needed since an expression such as, for example, 100 - X
can be written as 100 + (-1) * X
.
Define a function
removeSub :: Expr -> Expr
which removes all subtraction operators in an expression by replacing them with a combination of addition and multiplication as in the above example.
For example, 100 - X
would be represented by the expression
ex4 = BinOp Subtract (Num 100) X
Then removeSub ex4
should give
BinOp Add (Num 100) (BinOp Mul (Num (-1)) X)
Your definition should only remove the subtraction operators. It should not attempt to simplify or evaluate the expression in any way.
Hint: a correct solution must use recursion for every sub-expression in order to remove all subtraction operators.
The standard function isPrefixOf
tests whether a given list is a prefix of another. For example the following expression is true:
prop_isPrefixOf = "hell" `isPrefixOf` "hello"
&& [] `isPrefixOf` [1,2,3]
&& [1,2] `isPrefixOf` [1,2]
&& not ([2,3] `isPrefixOf` [1,2,3])
Define a quickCheck property
prop_take :: Int -> String -> Bool
which relates the function isPrefixOf
with the function take :: Int -> [a] -> [a]
. Your definition must use the two arguments as part of the test (so it is not OK to write a definition like prop_isPrefixOf
which just gives a fixed number of examples).
Consider the following code:
data Suit = Hearts | Clubs | Diamonds | Spades
deriving (Eq,Show)
data Rank = Numeric Int | Jack | Queen | King | Ace
deriving (Eq,Show)
data Card = Card Rank Suit
deriving (Eq,Show)
isRed, isDiamond :: Suit -> Bool
isRed s = s == Hearts || s == Diamonds
isDiamond s = s == Diamonds
isAce, isLow :: Rank -> Bool
isAce r = r == Ace
isLow (Numeric n) = n < 5
isLow _ = False
lowDiamonds cs = [Card r s | Card r s <- cs, isLow r && isDiamond s ]
redAces cs = [Card r s | Card r s <- cs, isAce r && isRed s ]
lowRedCards cs = [Card r s | Card r s <- cs, isLow r && isRed s ]
The last three functions in this code contain a lot of “cut-and-paste” repetition. Define a function
selectCards :: (Rank -> Bool) -> (Suit -> Bool) -> [Card] -> [Card]
which generalises these three functions, so that the following property holds:
prop_selectCards cs = lowDiamonds cs == selectCards isLow isDiamond cs
&& redAces cs == selectCards isAce isRed cs
&& lowRedCards cs == selectCards isLow isRed cs
Note: to check such a property with quickCheck we would need to define generators for cards. You do not need to worry about that.
Give the definition of a QuickCheck generator
quadlist :: Gen [Integer]
for lists of Integers, where for every list generated, the length of the list is a multiple of 4. I.e., the generated lists contain 0 numbers, or 4 numbers, or 8 numbers, or 12 numbers, and so on. Hint: QuickCheck function vectorOf :: Int -> Gen a -> Gen [a]
which generates a list of a specific length, as well as the generator arbitrary
may be useful, but replicate
or sized
should probably not be used.
Hints: (i) don’t make the common mistake of trying to apply a function of type Integer -> a
to something of type Gen Integer
, and (ii) don’t forget that you can work with things of type Gen Integer
using do-notation.
Part II
You do not need to work on this part if you only want to get a 3 or a G (although a correct answer to part II can be used instead of a question in part I).
The following definitions represent a shape composed of coloured squares arranged in a grid. This can be modelled as a list-of-lists, one for each row:
data Shape = S [Row]
type Row = [Square]
type Square = Maybe Colour
data Colour = Black | Red | Green deriving Eq
For example, a black L-shape might be represented by the following:
lshape = [[x,o]
,[x,o]
,[x,x]] where x = Just Black
o = Nothing
An alternative way to represent a shape is to use a coordinate system. Each coloured part of the shape is represented by a coordinate of a position in the grid, and the colour at that coordinate:
type AltShape = [Point]
data Point = P Colour (Int,Int) deriving Eq
In this representation, the L-shape above could be written:
altLshape = map (P Black) [(0,0),(0,1),(0,2),(1,2)]
Note that the alternative definition is not exactly equivalent, as does not give us a way to represent the blank squares; for example, all completely blank shapes, whether large or small, will be represented by the empty list. We will not worry about this minor difference in this question.
Define a function
fromShape :: Shape -> AltShape
that converts from a Shape
to an AltShape
, so that for example
fromShape lshape == altLshape
If your solution produces the correct points but listed in a different order that is also acceptable. You may assume, if necessary, that every row in the original shape has the same number of elements.
Consider the following definition of a binary tree
data Tree a = Branch (Tree a) a (Tree a)
| Leaf
deriving Eq
When using a tree to represent data it is often good if the tree is balanced, which means that there are roughly the same number of things in the left sub tree as there are in the right sub tree, for every branch in the tree.
We define the skew of a tree to be a measure of how unbalanced it is. Let us first define the skew of a branch in a tree: the skew of a branch (a non-negative number) is the difference between the number of things in the left sub-tree compared to the right sub-tree. Now we define the skew of a tree to be zero if the tree is a leaf, and the largest skew of all the branches in the tree otherwise.
For example, consider tree1 :: Tree String
tree1 = Branch (Branch Leaf "left" Leaf) "top" Leaf
The skew of the top branch is 1 and the skew of the left branch is 0, so the skew of tree1
is 1. Consider tree2
:
tree2 = Branch (Branch Leaf "left" (Branch Leaf "lr" Leaf)) "top" Leaf
there are three different branches, with skews 2, 1 and 0, respectively. So the skew of the whole tree is the maximum of these, namely 2.
Define a function
skew :: Tree a -> Int
which computes the skew of a tree. You may compute the skew in any way you like (i.e. it should be equivalent to the definition given above but it does not have to be defined in the same way).