RE-EXAM
Introduction to Functional Programming
TDA555/DIT440

 DAY: 2016-12-20 TIME: 14:00–18:00 PLACE: M-salar

 Responsible: Aids: Grade: David Sands; Questions:Alexander Sjösten 0317726167 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   (5 small assignments) Give good enough answers for 4 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! Do Part I and one assignment of your choice here and you will get a 4 Do Part I and both assignments here and you will get a 5 or a VG

 Please read the following guidelines carefully: Answers can be given in Swedish or English Begin each assignment on a new sheet Write your number on each sheet Write clearly; unreadable = wrong! 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 Never eat anything bigger than your own head

Good Luck!

Part I

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

1.

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

Complete the definition of the following function:

``````mostRain :: WeekNumber -> Double
mostRain n | n < 1     = 0
| otherwise =                       -- (complete this case)``````

such that `mostRain n` (when `n > 0`) gives the amount of rain in the rainiest week from week 1 up to and including week `n`.

For example, suppose that the rainfall in week 3 is 20.5 (`rainfall 3 == 20.5`). Now if week number 3 is the rainiest of the first 50 weeks, then `mostRain 50 == 20.5`.

Your solution must be recursive. Solutions that do not use recursion will be considered incorrect.

Hint: The function `max` may be useful. Note that you do not have to provide a definition for the function `rainfall`.

2. Define a function

``countLength :: Int -> String -> Int``

such that `countLength n s` returns the number of words in string s which have length n. The following property gives some examples:

``````prop_countLength1 = countLength 4 "live long and prosper" == 2
&& countLength 3 "eat and eat and eat"   == 5
&& countLength 2 "eat and eat and eat"   == 0``````

You should make use of the standard function `words`.

3. The following datatypes are used to represent a hand of cards:

``````data Suit = Hearts | Clubs | Diamonds | Spades
deriving Eq
data Rank = Numeric Int | Jack | Queen | King | Ace
deriving Eq
data Card = Card Rank Suit
deriving Eq

data Hand = Empty | Add Card Hand``````

Define a function

``moreAcesThan :: Hand -> Hand -> Bool``

where `hand1 `moreAcesThan` hand2` gives `True` if the number of aces in the `hand1` is more than the number of aces in `hand2`, and `False` otherwise (i.e. if the number of aces in both hands are the same, or if `hand2` has more aces than the `hand1`).

Hint: define a helper function which counts the number of aces in a given hand. The following simple definition might also be useful:

``rank (Card r _) = r``

4.

Write a QuickCheck property `prop_countLength` that relates `countLength n s` (from question 2) to the values of `length (words s)` and `length s` as follows: if there are `m` words of length `n` in `s` then `s` must have at least `n*m` characters, and there must be at least `m` words in `s`.

For example, `countLength 10 "absolutely fabulously" == 2`, and in this example there are at least 2 * 10 characters in that string (there are in fact 21), and there are at least 2 words (there are in fact exactly two).

5. Consider the following function:

``````rep :: Int -> String -> IO()
rep n s
| n <= 0    = return ()
| otherwise = do putStrLn s
rep (n - 1) s``````

This definition is not written in a good Haskell style since it uses more computation in `IO` than is really needed.

In this question you are to rewrite this function starting with the following incomplete definition:

``````rep :: Int -> String -> IO()
rep n s = putStr w
where w :: String
w =                                      -- complete this definition``````

The new version should behave the same as the old version when it is run. The definition of the missing local variable `w` must not use recursion. If your definition uses recursion it will be considered incorrect.

Hint: Use the standard functions `replicate` and `unlines`.

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

If you want to get a 4, you have to do Part I, plus one of the following assignments.

If you want to get a 5 or a VG, you have to do Part I, plus both of the following assignments.

6.

Tic-tac-toe, also called wick wack woe (in some Asian countries) and noughts and crosses (in the British Commonwealth countries) and X’s and O’s in the Republic of Ireland, is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a k by k grid (where k is usually 3). The X player goes first. The player who succeeds in placing k marks in a horizontal, vertical, or diagonal row wins the game. [description adapted from Wikipedia]

In this question we will consider the following representation of a tic-tac-toe grid:

``````data Play = O | X  -- The letter O not the number 0 (zero)
deriving Eq

data TicTac = TicTac Int  [[Maybe Play]]

exampleTT = TicTac 3 [ [Just O,  Just X,  Nothing],
[Just X,  Just O,  Nothing],
[Just X,  Nothing, Just O ] ]``````

Note that the Int parameter describes the intended size of the grid.

Define a function

``winner :: TicTac -> Bool``

which gives True if there is a winning line somewhere in the grid. For example, `winner exampleTT == True` because there are three `O`s in a line on one of the two diagonals.

You may assume that every TicTac grid of the form `TicTac n rs` that `rs` has `n` rows, and each row has exactly `n` elements. A winning line (vertical, horizontal, or diagonal), must have `n` identical plays

Note: Your solution must work for grids of any size. If it only works for grids of size 3 then your answer will be considered incorrect.

Hint:

• The function `transpose` may be useful.

7.

A kind of family tree can be represented by the following Haskell datatype:

``````type Name  = String
type Born    = Int
data Family = Fam Name Born [Family]``````

Here is an example Family:

``````duck :: Family
duck = Fam "Uncle Scrooge" 1898
[ Fam "Donald" 1932 [] ,
Fam "Ronald" 1933
[ Fam "Huey" 1968 [] ,
Fam "Duey" 1968 [] ,
Fam "Louie" 1968 [] ]
]``````

This value represents the male line of the duck family where Uncle Scrooge, born in 1898, had two sons, Donald and Ronald. Ronald has three children. Donald has no children, and Ronald has no grandchildren.

In a family tree, it would be impossible for some child to be born before their parent. Define a function

``isValidTree :: Family -> Bool``

which given a family tree, checks that every parent is born before they have children.

``````*Main> isValidTree duck
True

*Main> isValidTree \$ Fam "Walt Disney" 1901 [duck]
False``````

Note: Some ducks reach sexual maturity after just 20 weeks, so it is possible that a child is born in the same year as their parent.