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"
["http://www.chalmers.se","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.

5. Implement a Haskell function:

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.