1. (a)
(b)
(c)
(d)
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.
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.
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.
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”
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)
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 . 1
3. (a)
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.
(b) By building a type derivation, find the type of the term U.
(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.
(b) Explain the concept of backtracking in Prolog. Give an example Prolog program to demonstrate this concept.
(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.
(d) Give an example of a polymorphic type, overloading, and a subtype. Explain each example.
2