EXAM
Introduction to Functional Programming
TDA555/DIT440

 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 and Part II are both needed for a 4, 5, or VG

This exam consists of two parts:
 Part I   (7 small assignments) Give good enough answers for 5 assignments here and you will get a 3 or a G (Points on Part II can be counted towards Part I if needed, but this is very unlikely to happen in practice.) Part II   (2 larger assignments) You do not need to solve this part if you are happy with a 3 or a G! Pass Part I and one assignment of your choice here and you will get a 4 Pass Part I and both assignments here and you will get a 5 or a VG

 Please read the following guidelines carefully: Begin each assignment on a new sheet Write your number on each sheet Write clearly; unreadable = wrong! Comments (if needed) can be given in Swedish or English You can make use of the standard Haskell functions and types given in the attached list (you have to implement other functions yourself if you want to use them) You do not have to import standard modules in your solutions Tangentbordet är knepigt, men oftast har jag alt under ctrl.

Good Luck!

Part I

You have to complete 5 out of the following 7 assignments to get a pass on the exam.

## 1

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])``

## 2

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!

## 3

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``````

``data BusTicket = ...``

Note: you do not have to define any functions, or write any `deriving ...`.

## 4

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.

## 5

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

## 6

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.

## 7

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

## 8

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.

## 9

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