What is parametric polymorphism and why is it so common in Haskell?
Answer
Like generics in Java (0.5 marks) we can use type variables (0.5 marks) in Haskell to represent unconstrained, or arbitrary (0.5 marks) types for values. Effectively type variables are universally quantified (0.5 marks). It allows us to maintain static type safety (0.5 marks) while expressing computation in a generic way (0.5 marks), regardless of actual types (0.5 marks) max of 1.5 marks for the definition.
Due to Haskell’s powerful type inference system (0.5 marks), we can resolve type variables at compile time. The functional nature of Haskell (0.5 marks) and its widespread use of container data structures (0.5 marks) make polymorphism an efficient way to code generically. max of 1.5 marks for the explanation.
1b)
Abstract
Consider the Haskell functions with their type signatures listed below. For each function, give an actual function definition that would conform to the type signature shown. In each case, also give a short documentation-style explanation of the behaviour for the particular function you define.
(i) f :: a -> a
Answer
f x = x — identity function
(ii) g :: a -> b -> a
Answer
g x y = x — selector, return first of two parameters
(iii) h :: a -> [b]
Answer
h _ = [] — returns empty list for any input
(iv) i :: a -> b
Answer
i x = i x — bottom, infinite recursion (also accept function that throws an error)
1c)
Abstract
Now consider this Haskell function:
twice f x = f $ f x — apply f two times to x
(i) Give the Haskell type of the function twice and explain how you have inferred this type.
Answer
Type is twice :: (a->a)->a->a (0.5 marks, brackets must be correct). f is a function a→a that takes an arbitrary value (1 mark), we know its param has the same type as its result since the result of the first invocation becomes the param of the second invocation of f (1.5 marks)
(ii) Give the Haskell type of the expression (twice.twice) and explain how you have inferred this type.
Answer
Type is same as above — (a->a)->a->a (0.5 marks, brackets must be correct).
(.) is function composition, with type (b -> c)-> (a -> b)-> a -> c (0.5 marks)
now sub in type variables (0.5 marks for attempt)
a -> b has to match the type of twice, (t->t)->t->t, so a becomes t->t and b becomes t->t (1 mark)
same for b->c (0.5 marks)
so basically, a->c now becomes (t->t)->(t->t) which is just the original type (t->t)->t->t (0.5 mark)
same type, but function f will be applied four times now instead of twice… (0.5 marks)
(a->a)->a->a(a->a) -> (a->a) -> a -> a(a->a) -> a -> a
Question 2: Lists and Lazy Evaluation
Abstract
This question is about lists in Haskell. Note that, where you are asked to produce source
code, minor syntax errors will not be penalised so long as your intention is clear and correct.
2a)
Question
Give a Haskell definition for an infinite list of strings, yn :: [String], where every even indexed element of the list is the String value “yes” and every odd indexed element of the list is the String value “no”. Try to ensure your definition of yn is concise.
Answer
yn = "yes":"no":yn
Accept alternative solutions like: concat $ repeat ["yes","no"]
2b)
Question
Briefly discuss (in 50 words or fewer) the features of the Haskell language that enable the definition of such an infinite data structure.
Answer
Recursion, recursive definitions or recursive data structures
Laziness, lazy evaluation
2c)
Question
Give a QuickCheck property specification p::Int->Bool that could be used to test that odd indexed elements of list yn are equal to the String value “no”.
Answer
p = \x -> if x `mod` 2 == 1 && x > 0 then yn!!x == "no" else True
Lose 1 mark if part of compound condition for x is missing. 3 marks for correct solution.
2d)
Question
Will a test run of quickCheck p actually terminate? If so, why does it terminate? If not, why not?
Answer
Yes it will terminate (1 mark). Even though the list is infinite, QuickCheck only runs a finite number of test cases (1 mark).
2e)
Question
Give the Haskell definition for a function butter :: String -> String which appends the String value " but " onto its argument. For instance butter "head" will evaluate to "head but ".
Answer
butter x = x ++ "but "
2f)
Question
Now give the Haskell definition for a function uncertainty :: [String] -> String where the invocation uncertainty yn will evaluate to the String value "yes but no but yes but no but". You should use appropriate functions from the Haskell Prelude, along with the butter function from above.
Answer
uncertainty x = concat $ take 4 $ map butter x
1 mark for each Prelude function (x3), 1 mark for correct parameters, 1 mark for correct ordering / nesting of calls.
2g)
Question
Observe that the infinite list yn only contains two distinct values. Is it possible for a Haskell list to contain an infinite number of distinct values? If so, give an example list. If not, explain why not.
Answer
Yes, in principle infinite lists can all have distinct values
Although we will only ever compute a finite number of them due to the finite stack size, and the limited time
An example might be the Integer list [1..] or the list xs = “x”:(map (‘x’:) xs)
Question 3: Email API and Monads
Abstract
This question involves a scenario about sending emails. Some of the APIs are real, whereas
others are fictitious. You have encountered the real APIs throughout the course. The
question provides you with all the relevant documentation required to make use of the
fictitious APIs. Note that developing compilable Haskell code will simply take too long.
Minor syntax errors will not be penalised.
First, study the data type definition below. This is used to represent email addresses.
data Address = Address {
user :: String,
domain :: String
}
3a)
Question
Write Haskell source code to turn an arbitrary Address value into an appropriate String value, by means of implementing the Show typeclass. The generated String value should concatenate the user and domain values, with an ’@’ character in between them.
instance Show Address of show (Address user domain) = user ++ "@" ++ domain
Answer
instance Show Address where show (Address u d) = u ++ "@" ++ d
3b)
Question
Write Haskell source code, including an appropriate type signature, for getAddressFromUser, which prompts the user for a String value via interactive keyboard input and produces the appropriate Address value, if the input is valid. For the purposes of this question, you may assume that valid user input would be a String including a single ’@’ character, which is neither the first nor the last character. Your code should handle invalid input in a reasonable, idiomatic fashion for Haskell.
Note that you may make use of the splitOn API function:
splitOn
:: String — String to split on, error if empty
→ String — Input text
→ [String] — Result
— break input text String into pieces
— separated by the first String
— argument, consuming the delimiter.
getAddressFromUser:: IO (Maybe Address)getAddressFromUser = do input <- getLine parts = splitOn "@" input if length parts /= 2 then return Nothing else return $ Just $ Address (parts !! 0) (parts !! 1)
Answer
getAddressFromUser :: IO (Maybe Address)getAddressFromUser = do s <- getLine let parts = splitOn "@" s if length parts /= 2 then return Nothing else return $ Just $ Address (parts !! 0) (parts !! 1)
(accept alternative solutions, such as throwing exception or using Either)
3c)
Question
Now consider the following API functions:
mkMail
:: Address — sender email address (from)
→ Address — recipient email address (to)
→ String — email subject
→ String — email body
→ Email — result
sendMail
:: String — hostname of smtp server
→ String — username for login
→ String — password for login
→ Email — message to send
→ IO() — result
Why does the sendMail function have an IO result but the mkMail function does not have an IO result?
Answer
mkMail simply constructs a pure data structure, probably a bytestream in memory, no interactions with outside world (1 mark)
sendMail communicates with the SMTP server, which is a visible side-effect (1 mark)
3d)
Question
Study the following specification carefully, then write Haskell code to meet this specification.
You may find it helpful to use higher-order list functions like map, mapM, mapM_, or similar.
Your task is to produce an implementation of the function sendEmails :: [Address] -> IO (). This function prompts the user for input with a question:
‘what is your email address?’ then receives an answer using getAddressFromUser
as defined above. If the input email address is not valid, the function sets the sender
address to “noreply@gla.ac.uk”. Now the code should construct an email to
send to each of the addresses in the list supplied as the parameter of the sendEmails
function. Each of these emails should come from same sender address. Each of these
emails should have a subject set to the String value “Hello” and a body set to the
String value “I hope your exam is going well.”. The emails should all
be sent via the server smtp.gla.ac.uk with username foo and password secret.
There are lots of possible solutions to this exercise. Marks will be awarded for correctness,
as well as for idiomatic, elegant functional code.
sendEmails :: [Address] -> IO ()sendEmails emailList = do putStrLn "What is your email address?" givenAddress <- getAddressFromUser let userAddress = case givenAddress of Nothing -> (Address "noreply" "gla.ac.uk") (Just a) -> a let emails = map (\x -> mkEmail givenAddress x "Hello" "I hope your exam is going well") emailList mapM_ (\x -> sendMail "smtp.gla.ac.uk" "foo" "secret" x) emails
Answer
sendEmails :: [Address] -> IO ()sendEmails addresses = do putStrLn "what is your email address?" myAddress <- getAddressFromUser let fromAddress = case myAddress of Nothing -> (Address "noreply" "gla.ac.uk") (Just a) -> a let emails = map (\x -> mkMail fromAddress x "Hello" "I hope your exam is going well.") addresses forM_ emails (sendMail "smtp.gla.ac.uk" "foo" "secret") -- 1 for forM_ or similar iteration over emails
— 1 for sendMail with args
— 2 for point-free, lets, and/or other elegant style