(a) Give the type of f1, explain what the type means, and give the value of test_f1, where the definitions are:
f1 k xs = [x-k | x <- xs, x>k]test_f1 = f1 2 [3, 4, -3, 1, 2, 7]
Answer:
Type: f1 :: (Num a, Ord a) => a -> [a] -> [a]
The type means that the function takes two arguments: a value of type a, and a list whose elements have type a; a can be any type provided that it is in the Num class and in the Ord class. The function returns a list of the same type.
Value of test_f1: [1, 2, 5]
(b) Give the type of f2 and the value of test_f2:
f2 f g h = f . g . htest_f2 = f2 (*5) (+1) (*2) 3
Answer:
Type: f2 :: (c->d) -> (b->c) -> (a->b) -> a -> d
Value of test_f2: 35
(c) Give the type of f3 and show how you infer the type.
f3 (a,b) [c,d,e] = (a+b, c+d<e)
Answer:
Type: f3 :: (Num a, Num b, Ord b) => (a,a) -> [b] -> (a, Bool)
Variables a, b must have the same type a which must be in Num because (+) :: Num a ⇒ a → a → a. Variables c, d, e must have the same type b which must be in Ord because (<) :: Ord a ⇒ a → a → Bool. Hence the argument type must be (a,a) and [b] and the result type must be (a,Bool).
(d) Give the type and definition of the map function.
Answer:
map :: (a->b) -> [a] -> [b]map f [] = []map f (x:xs) = f x : map f xs
(e) Suppose a Haskell program contains the following definitions:
n = 3 + nxs = [if x==3 then n else x | x <- [0..5]]k = length xs
Give the values of n, xs, and k. For any undefined value, write bot (for bottom). If k is bot, explain why; if it is not, explain how its value is computed.
Answer:
The value of n is bottom (undefined) because the addition requires the value of n, and this cannot be computed before the addition is performed. Thus n has a circular definition that cannot be computed.
The list xs has the value [0, 1, 2, bot, 4, 5]; thus the list itself is not bottom, but one of its elements is bottom.
The value of k is 6, which is defined because the length function only examines the list structure and does not need to use any of the values in the list.
with value [1, 2, 3, …] which is infinitely long. (i) Write a definition of posInts.
Answer:
posInts :: [Int]posInts = let f x = x : f (x+1) in f 1
(ii) Explain how lazy evaluation makes it possible to define infinite data structures like posInts.
Answer:
Without lazy evaluation, the expression f 1 would never return a value; it would go into an infinite loop filling up memory with the list. Lazy evaluation causes a closure to be returned, which is a representation of how to compute more of the result when needed. Only as much of the list will be constructed as actually needed by the program.
Question 2: Embedded Domain Specific Languages
(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.
(b) Consider a type Colour defined as follows:
data Colour = Red | Green | Blue
(i) Define a function hot :: Colour → Bool, so that hot returns True if its argument is Red, and returns False if its argument is not Red.
Answer:
hot :: Colour -> Boolhot Red = Truehot Green = Falsehot Blue = False
(ii) Give the necessary declarations so that Colour is a member of the Show class, and the result of showing Red, Green, or Blue is "R", "G", or "B" respectively.
Answer:
instance Show Colour where show Red = "R" show Green = "G" show Blue = "B"
(c) Write a parser vname :: Parse String that matches an access to a variable name that must begin with a letter, may contain any number of additional letters, followed by any number of digits. However, a letter is not allowed after a digit. Thus "ab345", "x", and "znv6" are all valid, but "34", "ab37q", and "*x7" are not valid.
Answer:
var :: Parse Stringvar = do x <- letter xs <- many letter ys = many digit return (x : (xs++ys))
(d) Consider the following definition:
data Tree = Tip Int | Node Int Tree Tree
(i) A binary search tree is a Tree such that all the numbers in the left subtree of a node are less than the Int in that node, and all the numbers in the right subtree are greater than the Int in that node. Write a constant bst1 :: Tree which is a binary search tree, and write a constant notbst1 :: Tree which is not a binary search tree. Both values should contain at least two Nodes.
(ii) Write a function searchBst :: Int → Tree → Bool, such that searchBst n t returns True if n appears in t, and False otherwise, provided that t is a binary search tree. In the worst case, the function should take time proportional to the depth of the tree. If the argument t is not a binary search tree, then the result is not required to be correct.
Answer:
searchBst n (Tip x) = n==xsearchBst n (Node x a b) = n==x || searchBst n (if n<x then a else b)
(iii) Write a function search :: Int → Tree → Bool, such that search n t returns True if n appears in t, and False otherwise. The argument t does not need to be a binary search tree. Estimate the worst case time required by search.
Answer:
search n (Tip x) = n==xsearch n (Node x a b) = n==x || search n a || search n b
The worst case time for search is proportional to the number of elements in the tree.
(e) Simplify the following lambda expression. Show each step in the reduction, and for each step show which conversion rule you are using.
(a) Consider the following definition of func. The types for MyMaybe, myHead, and myTail are given below.
func :: [a] -> MyMaybe afunc xs = do a <- myTail xs b <- myTail a c <- myHead b return cdata MyMaybe a = MyNothing | MyJust amyHead :: [a] -> Maybe amyTail :: [a] -> Maybe [a]
Give the types of the monadic functions >>= and return, and explain what they do. Translate func into a functional definition that uses the monadic functions return and >>=, and that does not use the “do” syntax.
Answer:
class Monad m where (>>=) :: m a -> (a -> m b) -> m b return :: a -> m a
= takes a monadic action that yields a result of type a, and a function that takes a value of type a and returns a new monadic action that yields a result of type b. It runs the first action, passes the result to the second action, runs it, and returns the results.
return takes a value of type a, and returns a monadic action that, when performed, will yield that value. Thus it takes a value and puts it into the monad.
func xs = myTail xs >>= (\a -> myTail a >>= (\b -> myHead b >>= (\c -> return c)))
(b) Assume that the list xs has a finite (but unbounded) number of elements. Prove that sum (map (2*) xs) = 2 * sum xs. Use the following definition of sum:
sum :: Num a => [a] -> asum [] = 0sum (x:xs) = x + sum xs
Answer:
Proof by induction over xs.
Base case []. sum (map (2*) []) = sum [] = 0 = 2*0 = 2 * sum [].
Induction case, using statement of theorem as hypothesis.
sum (map (2*) (x:xs)) = sum (2*x : map (2*) xs) = 2*x + sum (map (2*) xs)
= 2*x + 2 * sum xs = 2 * (x + sum xs) = 2 * sum (x:xs)
(c) Suppose a Haskell program contains the expression f exp1 exp2. Explain why the result is guaranteed to be correct even if the arguments are evaluated in parallel. Explain why, in general, the arguments to procedures in an imperative language cannot be evaluated in parallel.
Answer:
A pure functional language, such as Haskell, satisfies the Church Rosser property, because it has no side effects (i.e. the language is, at its core level, the lambda calculus). This means that any order of evaluation will yield the same result, as long as that order achieves a result. In particular, this means that if an expression has several redexes, they can be evaluated in any order, including parallel order, without affecting the result. Consequently, the language implementation is free to use parallelism without running the risk of producing incorrect results.
In an imperative language, the expressions may be calls to procedures that make assignments to global variables, and the result may depend on the order of assignments. For this reason, a strictly defined order (e.g. left to right) is needed to obtain a uniquely defined result, and parallel evaluation may give a different answer than sequential evaluation.
(d) Define the term referential transparency, and explain why Haskell has referential transparency even if mutable IORef variables are used.
Answer:
Referential transparency means that if e1=e2, then for all exp, exp[e1/e2] = exp (provided that the expressions are all well typed). In other words, referential transparency means you can “substitute equals for equals” without changing the meaning of a program.
Imperative languages do not have equations, so they lack referential transparency. (Alternatively, if one thinks that an assignment statement in a language like C or Java is an equation because it looks like one, you can prove that 0=1 by simple algebra; imperative languages are not referentially transparent.)
The reason that Haskell is referentially transparent even if you have IORefs in an IO monad is that the terms denote computations of type IO a, not ground values of type a. Thus equational reasoning can be used to prove that two computations are equivalent, but not to obtain contradictions like 0=1.
Question 4: Interactive Programming
(a) Write an interactive program called prog. It promts the user to enter a number (of type Double). If the user enters the character 'q' the program prints "Bye" and stops. If the user enters a number, the program prints the count of numbers so far, and their mean, and then prompts the user for more input. The program does not need to handle incorrect input data. For example:
*Main> prog
Enter a number: 3
Count is 1, mean is 3.0
Enter a number: 6
Count is 2, mean is 4.5
Enter a number: q
Bye
Answer:
prog :: IO ()prog = helper 0 []helper :: Int -> [Double] -> IO ()helper count xs = do putStr "Enter a number: " xs <- getLine if head xs == 'q' then do putStrLn "Bye" return () else do let x = read xs :: Double let mean = sum (x:xs) / (count+1) putStrLn ("Count is " ++ show (count+1) ++ ", mean is " ++ show mean) prog (count+1) (x:xs)
(b) Consider the head and tail operations on lists. (i) Define the term partial function. Explain why head and tail are partial.
Answer:
A partial function is undefined on some elements of its domain. Head and tail are partial, because they are undefined when applied to the empty list.
(iii) The function f xs = head (tail xs) is partial. Define a total function safe_f, using the Maybe monad, which is similar to f. If f xs is defined, then safe_f xs = Just (f xs); if f xs is undefined, then safe_f xs = Nothing.
(iii) Discuss the tradeoffs between using the Maybe monad for computations that might fail, and using an exception handler.
Answer:
The Maybe approach guarantees that every operation is checked, and it identifies exactly where a computation fails. Thus it gives a precise determination of the location of a failure. However, it requires the code to be expressed using Maybe types and in the monadic style, and checking every operation requires some computation time. The exception handler does not identify precisely where a computation failed, but it does not require the code to be written in a special style.
(c) Suppose a program with a graphical user interface has a global state that needs to be updated when an event occurs. The program has a number of buttons; when a button is pressed, a computation takes place which may update the global state. State whether an MVar or an IORef would be more appropriate for maintaining the global state. Justify your answer.
Answer:
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.