COM2108 Functional Programming Autumn 2020
Solutions to Final Exercise Set
This final set of exercises is of a different style, reflecting the advanced topics that you saw in the last couple of weeks of the module. The focus here is more on principles than application – if you’ve got this far, you should have a good grounding in functional programming principles (evidenced by your performance in the threshold tests). The depth of your knowledge will be evidenced by your performance in the programming assignment and the exam. The questions here relate to those advanced topics that you can expect to see on the exam.
Exercises
1. The Haskell wiki (wiki.haskell.org) says “Haskell separates pure functions from computations where side effects must be considered by encoding those side effects as values of a particular type. Specifically, a value of type (IO a) is an action, which if executed would produce a value of type a.”
Say you were asked to write a program that takes as input the name of a file containing the names and email addresses of people (as a comma-separated list), reads in the file contents, then prompts the user for a name to look up, printing out the corresponding email address (if it exists), or the message “
Sketch (in diagram form or pseudo-code) a Haskell-based solution, clearly indicating the types of the functions that would be required. In particular, those functions that involve IO must be clearly indicated.
Answer:
For the top level function, we need to take a single argument (a String, representing the file name). It will not return anything, but because it needs to perform IO actions, must have return type IO (). This function will call a function to read the file, then a function to prompt the user for the name to look up and print the result.
For the input file, we need a function to read it. This function needs to return a list of (name, email address) pairs, but because it is reading from a file, it needs to have return type IO [(String,String)]. It should take a single argument: the file name, a String.
For the lookup, we need a function that takes the list of (name, email address) pairs, prompts the user for the name to lookup, then searches the list for a pair with the first item being the name, printing the second item if it is found, or the error message otherwise. Like the top level function, this function does not need to return anything, but because it is performing IO actions (prompting the user and reading their input), it needs to have return type IO ().
You could give further low level details if you wanted, but everything below this is fairly straightforward.
1
COM2108 Functional Programming Autumn 2020
2. What principles would you use to test your program? I am not looking for specific values, but the rationale behind why you would choose specific values for testing. Do not think about just the top level function, but also the lower-level functions that were part of the solution you sketched above. How will you ensure it gives correct behaviour in all situations?
Answer:
To test the file input function: Check what happens if the file does not exist, if the file is in the wrong format, if the file is empty, if the file has incorrect permissions (cannot be read), and check that it can read a valid file with data in it.
To test the lookup function: Check if the name can be found, if the name cannot be found, if the input file (and hence the list) was empty. When checking if the name can be found, check for several different positions in the data: first, middle, last.
You would also want to make sure that the top level function works, but this should be straightforward once the above functions have been tested.
3. Consider this definition of a Binary Tree:
data Tree a = Leaf
| Node (Tree a) a (Tree a)
instance Foldable Tree where
foldMap f Leaf = mempty
foldMap f (Node l x r) = foldMap f l `mappend` f x `mappend` foldMap f r
foldr f acc Leaf = acc
foldr f acc (Node l x r) = foldr f (f x (foldr f acc r)) l
This is a minimal definition that would allow the application of, for example, the toList function that is part of the Foldable class. Explain how this is possible. (Note: this does not require you to provide any Haskell code; explain the principle.)
Answer:
This is a different definition of a type for a binary tree to that which we looked at in the lectures, but the same principles apply. The minimal definition of an instance of the Foldable class is a definition for foldMap or foldr. In this case, both have been provided, but either would have been sufficient. If only foldMap was provided, foldr could be derived from it, and vice versa. These are not the only two functions provided by this class though: many others – typically functions that you associate with lists – can also be derived, given either of these definitions.
2