(a) Give the type of f1, explain what the type means, and give the value of test_f1, where the definitions are:
f1 g xs = map g ((map (2*) xs)test_f1 = f1 (7+)[3, 4, -3, 1, 2, 7]
Answer:
f1 :: (Num a) => (a->a) -> [a] -> [a]
test_f1 = [13, 15, 1, 9, 11, 21]
The type means that the function takes two arguments: a function that takes a value of type a and returns another value of the same type, and a list whose elements have type a; a can be any type provided that it is in the Num class. The function returns a list of the same type. [1 mark for the type, 1 mark for the value.]
(b) What is the type of 2 in general? In the expression 2 * 3.14, assume that 3.14 :: Double. What is type type of 2 in this expression? Is it converted to Double at runtime?
Answer: 2 :: Num a ⇒ a which means that it is a polymorphic constant that can have any numeric type. In the expression given, 2 :: Double because the two operands to * must have the same type. There is no cast or runtime conversion. [Straightforward; requires knowing about numeric type classes.]
(c) Give the type of f3 and show how you infer the type.
f3 (a,b) [c,d,e] = if a<b then c+d else d-e
Answer:
f3 :: (Ord a, Num b) => (a,a) -> [b] -> b
Variables a, b must have the same type a which must be in Ord because (<) :: Ord a ⇒ a → a → a. Variables c, d, e must have the same type b which must be in Num because (+) :: Num a ⇒ a → a → a.
[Requires understanding of type inference and type classes.] [1 mark for the function type, 1 mark for the class constraints, marks for the explanation of the inference.]
(d) Give the type and definition of the foldr function.
Answer:
foldr :: (a->b->b) -> b -> [a] -> bfoldr f a [] = afoldr f a (x:xs) = f x (foldr f a xs)
[Bookwork.] [1 mark for type, 1 mark for definition.]
(e) Explain the difference between an equation in Haskell and an assignment statement in an imperative language. Discuss how Haskell programs can perform computations, even though they cannot modify the values of variables.
Answer: An assignment is a command to evaluate the right hand side and then to store the result into the left hand side, discarding the old value. An equation is an assertion that the left and right hand sides have the same value. An equation can be used to define a variable, but not to change it. Haskell programs operate by calculating new values and binding them to new names (or commonly, to the same name in a different scope corresponding to an iteration of a recursive function).
[Requires understanding. 2 marks for difference between the two; 2 marks for how computation is performed.]
with value [1, 2, 1, 2, …] which is infinitely long. (i) Write a definition of onetwo. (ii) Give the value of (take 5 (map (3*) onetwo)), and explain how it can be evaluated even though onetwo is an infinite list.
Answer: (i)
onetwo :: [Int]onetwo = 1 : 2 : onetwo
(ii) [3, 6, 3, 6, 3] This is possible because of lazy evaluation. Onetwo requires only two cells to represent, with a circular pointer. The map defines an infinite list, but only the part that is needed is computed, and take needs only 5 elements. [Requires understanding lazy evaluation.]
Question 2: Domain Specific Languages and Parsec
(a) Define the term embedded domain specific language. Give three examples of Haskell features that are useful for implementing EDSLs, and explain why they are useful.
Answer: A DSL is a language designed specifically for an application area (the “domain”), and its constructs and notation are aimed at that application area, not for general purpose programming. An EDSL is a DSL that is implemented by embedding it in a general purpose language, such as Haskell; this means that the existing Haskell tools can be used to compile the EDSL. Thus an EDSL is based on a library rather than a compiler. To make this possible, the host language needs to have flexible syntax and semantics. Haskell’s algebraic data types enable a library to define data structures that are suitable for an application domain. Type classes enable the semantics of operations like showing, reading, comparison, etc. to be adjusted to suit the needs of the EDSL. Monads provide the ability to define new control structures as needed. Templates allow code to be generated from new syntactic constructs. Operator definitions allow expressions to be targeted to the application area.
[The term is bookwork. A few examples have been discussed in lectures, but many more are apparent with some thought.] [1 mark for definition, 1 mark for each feature explanation.]
(b) Explain the basic concept behind the Parsec parser combinatory library, and give a four examples of different combinators and their usage.
Answer: Parsec is monadic parser combinatory library. With Parsec, parsers are constructed by combining higher-order combinators to create larger expressions. Combinators are functions without free variables, the way they are used in Parsec’s monad they take no explicit arguments. Examples are many1, string, parens.
[Requires knowing the basics of Parsec (1) + 1 mark for every example]
(c) How is a choice of parsers expressed in Parsec? What role does the "try" combinatory play? Provide a complete string parsing example that uses both.
Answer: Choice is expressed using the <|> combinatory. Normally if a parse of an option is performed and partially succeeds, it consumes the parsed input. The “try” combinator allows to parse without consuming the input if the parse fails.
[This is similar to examples that have been discussed in lectures.] [2 marks for explaining choice and try; 1 mark for use of Parse monad, 2 marks for accepting the specified syntax.]
(d) Write a Parsec-based parser to parse a sentence into a list of lowercase words. The resulting list should only contain the words, no punctuation characters.
Answer:
getWords :: Parser [String]getWords = do words <- sepBy1 word space return map lcNoPunct wordsword = many1 letterlcNoPunct word = filter (\c -> not (c `elem` ['.','?','!',';',',','—']) ) (map toLower word)
[Straightforward use of Parsec combinators, map and filter. 2 marks for each, meaning and syntax]
Question 3: Monads and IO
(a) Consider a function f which computes the value of (x*y) / z. However, in order to avoid the possibility of an exception (overflow or division by 0), f uses safeMult and safeDiv to perform the calculations. Their types are given below. Write two definitions of f :: Double → Double → Double → Maybe Double using the Maybe monad: a definition using a do expression, and an alternative definition using the >>= operator.
myMult, myDiv :: Double -> Double -> Maybe Double
Answer:
func :: a -> a -> a -> Maybe afunc x y z = do a <- safeMult x y b <- safeDiv a z return cfunc x y z = safeMult x y >>= (\a -> safeDiv a z >>= (\b -> return b))
[Requires knowing the monadic operations (2 marks for types, 2 marks for explanation), and the desugaring rules for do (2 marks).]
(b) Assume that the list xs has a finite (but unbounded) number of elements. Prove that map f (map g xs) = map (f . g) xs
Answer: Proof by induction over xs.
Base case [].
map f (map g []) = map f [] = [] = map (f . g) []
Induction case, using statement of theorem as hypothesis.
map f (map g (x:xs) = map f (g x : map g xs) = f (g x) : map f (map g xs) = (f . g) x : map (f . g) xs = map (f . g) (x : xs)
[Requires understanding and ability to carry out equational reasoning.] [1 mark for base case, 2 for setup, 1 for use of hypothesis, 2 for accuracy and completeness.]
(c) Explain why equational reasoning can be used to prove theorems about programs in Haskell, it cannot be used to prove theorems about programs in an imperative language.
Answer: Equational reasoning requires that equations denote pure equality, so that if exp1 = exp2 then the two expressions are interchangeable. This property is called referential transparency, and Haskell satisfies it. Imperative languages do not have this property because variables are mutable, so an equation may be true at one point during the execution of a program but untrue at another point. [Bookwork.]
(d) Explain how IORef variables are used in a Haskell program with a graphical user interface implemented with gtk. Explain why the Haskell program satisfies referential transparency even though it contains IORef variables.
Answer: The program needs to have a global state, which is kept in an IORef. It is impossible to hold the state in an argument to a recursive function, or as a monadic state (the two most common ways to represent state) because the order of events depends on the order in which the user clicks on GUI controls, and this is outside the control of the program. However, when an event is triggered, that event performs a monadic computation with referential transparency. Thus the program executes as a collection of separate computations, which are triggered by the outside world. As the program initializes the GUI, it performs a sequence of monadic operations, again with referential transparency. Furthermore, even though the IORef variable is mutable, it remains the case that any two expressions that are equal are interchangeable. Referential transparency does not preclude mutable variables or I/O side effects. [This topic is discussed in depth in lectures. This question is bookwork, but it takes significant understanding to be able to give the answer.]
Question 4: Imperative Style in Haskell
(a) Why does the following code not work in Haskell? (Assume that rand is a function returning a pseudo-random number between 1 and 10.)
let a=0 bs=[] bs = map rand [1..10] a = a + bs !! 0 a = a * bs !! 1 bs !! 2 = bs !! 0 + bs !! 1 a = a - b !! 2in a
Answer: This code does not work because (i) variables in Haskell are immutable (ii) the lhs of an assignment can’t be an expression (iii) lists are also immutable
[This requires understanding the concept of immutable variables and the meaning of the assignment symbol in Haskell.]
(b) (i) Explain two mechanisms for handling state in Haskell and explain their use and differences. (ii) Use one one of them to create equivalent imperative-style code for a) that will work correctly
Answer: (i) For example:
An IORef is a mutable variable whose access is controlled by the IO monad. An IORef must be created with an initial value; reading an IORef does not modify it. If IORefs are used in a concurrent or parallel program, it is possible for there to be a race condition, resulting in undefined semantics.
An MVar is a mutable variable that can be either full or empty, and is intended for use in concurrent programs. If a thread attempts to read an MVar, it is blocked until the MVar becomes full. If a thread takes an MVar, the MVar becomes empty and the thread continues execution with the value that was in it. When a thread writes to an empty MVar, it becomes full and if a thread was blocked reading it, that thread is awakened. MVars provide mutable state with locking, so multiple threads can share state safely, without allowing race conditions.