1. (a)
G6021: Comparative Programming
Exam Practice 4
Write a function first in Haskell that takes as parameters a number n and a list of numbers l, and returns the first n elements of the list l. The following shows the expected behaviour:
first 3 [9,2,4,7,6,5] = [9,2,4]
first 0 [1,2,3,4,5,6,7] = []
first 10 [1..] = [1,2,3,4,5,6,7,8,9,10]
You can assume that the input list l is longer than n, and you should include the type of your function in your answer.
Answer:
first :: Integer -> [Integer] -> [Integer]
first n (h:t) = if n==0 then [] else h:first (n-1) t
Write a function filt that takes a number n and a list of numbers, and returns the list with all the multiples of n removed. You can make use of a built-in function mod that gives the remainder after division (mod 2 2 = 0, mod 3 2 = 1). The following shows the expected behaviour:
filt 2 [1,2,3,4,5,6] = [1,3,5]
filt 1 [1,2,3,4] = []
filt 3 [1..10] = [1,2,4,5,7,8,10]
Include the type of your function in your answer.
Answer:
filt :: Int -> [Int] -> [Int]
filt n [] = []
filt n (h:t) = if h ‘mod‘ n == 0 then filt n t else h:filt n t
Starting with the list [2..], we can generate a list of prime numbers by repeatedly doing the following two steps:
i. Keep the first element of the list (say h) as this is a prime number. ii. Delete all multiples of h from the remaining list.
Write a function primes that will generate all the prime numbers. Include the type of your function in your answer, and give a Haskell expression to generate the first 100 primes.
Answer:
primes :: [Int] -> [Int]
primes (h:t) = h:primes(filt h t)
first 100 (primes [2..])
Give the output for each of the following Haskell expressions. Include a brief (1 or 2 sentences) explanation to justify your answers.
i. [x | x<-[1..], x<6]
ii. map (\(x,y) -> x*y) [(1,3),(4,5),(1,9)]
iii. foldr (\x -> \y -> 1+y) 0 “testing” 1
(b)
(c)
(d)
iv. f [3,4,1,2] [], where f is defined as: f [] acc = acc
f (h:t) acc = f [x | x <- t, x<=h]
(h:f [x | x <- t, x>h] acc)
Answer:
Some working should be shown (partial marks may be awarded):
i) [1,2,3,4,5,6, (does not terminate)
ii) [3,20,9]
iii) 7
iv) [1,2,3,4]
2. Consider the λ-term BUV where
• B = λxyz.x(yz)
• U = λx.xII
• V = λyx.x(λx.xy) • I = λx.x
(a) Draw the β-reduction graph of BUV . Answer:
(λxyz.x(yz))U V c
(λyz.U (yz))V
(λyz.(yz)II)V λz.U(V z)
λz.(V z)II λz.U(λx.x(λx.xz))
λz.(λx.x(λx.xz))II c
λz.I(λx.xz)I c
λz.(λx.xz)I c
λz.Iz
c
λz.z
(b) By building a type derivation, find the type of the term U.
2
‘
‘
‘
EE
EE
Answer:
Inthefollowing,T =((A→A)→(B→B)→C):
x : T,z : A ⊢ z : A x:T⊢x:((A→A)→(B→B)→C) x:T⊢I:A→A x:T,z:B⊢z:B
x : T ⊢ xI : (B → B) → C x : T ⊢ I : B → B x : T ⊢ xII : C
⊢ λx.xII : ((A → A) → (B → B) → C) → C
(c) Explain how to represent Booleans in the λ-calculus by giving λ-terms for TRUE, FALSE, and the function NOT. Show that NOT FALSE reduces to TRUE in your representation.
3. (a)
Answer: Part bookwork. We can represent Boolean values: • F alse = λx.λy.y
• T rue = λx.λy.x
and Boolean functions. The function NOT is defined by NOT = λx.x False True
We can check that this definition is correct: • NOT False = (λx.x False True)False • →β False False True
• →∗β True
Describe the main differences between variables in imperative languages and variables in declarative languages such as Haskell and Prolog. Include examples to illustrate your answer.
Answer:
The answer should mention that variables in imperative languages are abstrac- tions of memory cells, with associated attributes such as address and value, which can be updated whereas in declarative languages they represent ex- pressions or unknown parts of the program, e.g. parameters for predicates or functions, and there is no assignment command. Logic variable can be unified, thus give output as well as input.
(b) Explain the concept of backtracking in Prolog. Give an example Prolog program to demonstrate this concept.
Answer: When there are two rules that can apply, Prolog will try them both in order. Backtracking is the process of returning to this choice point to try the alternatives. Example: there are two rules for p:
r.
s.
a.
p :- a,b,c
p :- q,r.
q :- s.
?p
(c) Write Prolog clauses to decide if a list is sorted in ascending order. Give a trace of your clauses for the query to decide if the list [1,3,2] is in ascending order. Your trace should show the substitutions at each step.
Answer:
3
isOrdered([]).
isOrdered([_]).
isOrdered([A,B|T]) :- A <= B, isOrdered([B|T]).
The trace of the query:
isOrdered([1,3,2])
A = 1, B=3, T=[2]
1<=3, isOrdered([3,2])
A = 3, B=2, T=[]
3<=2, isOrdered([2])
FAIL
(d) Give an example of a polymorphic type, overloading, and a subtype. Explain each example.
Answer: Mostly bookwork.
The function len, below, is polymorphic because the same code is executed no matter what the types of the list are.
len [] = 0
len (_:t) = 1+len t
len :: (Num t1) => [t] -> t1
Overloading: 1 + 4, 1.2 + 3.7. Known also as ad hoc polymorphism. Subtyping – if object A has all the functionality of another object B, we can use A in place of B in contexts expecting A. Subtyping means that the subtype has at least as much functionality as the base type.
4