EXAM
Introduction to Functional Programming
TDA555/DIT440

 DAY: 2016-10-29 TIME: 14:00–18:00 PLACE: M-salar

 Responsible: Aids: Grade: David Sands, D&IT, Tel: 0737 20 76 63 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

Good Luck!

Part I

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

1.

Given the following definition:

``````af :: Num a => [a] -> [a]
af []       = []
af [x]      = [x + 1]
af (x:y:xs) = (x + 1) : y : af xs``````

what answer do we get when we give the following expression to ghci:

``af [10,20,30]``

2. Implement a function

``urls :: String -> [String]``

that given a text (as a string), returns a list with all web addresses (URLs) in that text. We say that web addresses are words that start either with the string “http://” or with “https://”.
Your solution must take care of both of these cases.

Examples:

``````*Main> urls "First try http://www.chalmers.se then try https://www.google.com"

*Main> urls "It's fun to stay at the Y.M.C.A."
[]``````

Hints:

• To check whether a string starts with e.g. “http://” you can use the standard function `isPrefixOf`. The expression `isPrefixOf p s` checks whether the string `s` begins with the string `p`.
• You should use the standard functions `words`.

3. Give a definition of a Haskell data type that can be used to represent arithmetic expressions such as the following four examples:

``````3 * (2 + x) * y
x + 2 * y
2 * 3
42``````

Your data type should be suitable to represent arithmetic expressions of any size built using multiplcation, addition, integers, and variables `x` and `y` only. You should not be able to represent variables other than `x` and `y` in your data type, or any invalid expressions.

4. Function `lookup` is one of the standard functions. Write a QuickCheck property `prop_LookJust` that expresses that if `lookup x table` gives a result `Just y`, then the pair `(x,y)` should actually be in the table.

Hints:

• You should be careful to make sure that `prop_LookJust` never gives an error (assuming a correct definition of `lookup`).
• The standard function `elem` can be useful here.

``wordCount :: FilePath -> IO (Int,Int)``

that given a file name, counts the number of words and lines in that file, and returns them as a pair (in that order).

Example:

``````*Main> wordCount "ExamAnswers.hs"     -- (a file with 331 words and 96 lines)
(331,96)

*Main> wordCount "emptyfile.txt"           -- (a file that contains nothing)
(0,0)``````

Hint:

• You will need to use standard functions `readFile`, `words`, and `lines`.

Part II

You do not need to work on this part if you only want to get a 3 or a G!

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

``showTicTac :: TicTac -> String``

so that for example

``````*Main> putStr (showTicTac exampleTT)
O|X|
-----
X|O|
-----
X| |O``````

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. You should print the grid exactly as above.

Hint: the functions `intersperse` and `unlines` could be useful here.

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.

Define a function

``parent :: Name -> Family -> [Name]``

which given a name of a person and a family tree, finds all the possible parents of the person in the tree. So, for example,

``````*Main> parent "Duey" duck
[Ronald]

*Main> parent "Uncle Scrooge" duck
[]

*Main> parent "Bob" duck
[]``````

If the child’s name appears several times in the family tree then there could be more than one possible parent.