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 (5 small assignments)
|
Part II (2 larger assignments)
|
Please read the following guidelines carefully: |
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:
isPrefixOf
. The expression isPrefixOf p s
checks whether the string s
begins with the string p
.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:
prop_LookJust
never gives an error (assuming a correct definition of lookup
).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:
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.