Department of Computer Science University College London
Example conversion of the 2017 exam paper into “Multiple-Choice” style with three compulsory questions
This is NOT a real exam paper!
Functional Programming
Copyright By PowCoder代写 加微信 powcoder
Time allowed 2.5 hours
Standard calculators are allowed Answer ALL THREE questions
COMP3011/COMPGC16: Functional Programming, example paper
Answer all THREE questions
Marks for each part of each question are indicated in square brackets. Calculators are permitted
1. (a) Consider the following Miranda code for an algebraic type called “expr”: expr ::= Var [char] | App expr expr | Lambda [char] expr
You are told that this algebraic type is used to model expressions in a version of the lambda calculus.
(i) Which version of the lambda calculus is modelled? Choose one of the following answers:
A. No version because the code has an error
B. The typed lambda calculus with constants
C. The typed lambda calculus without constants D. The untyped lambda calculus with constants
E. The untyped lambda calculus without constants
(ii) Which one of the following Miranda expressions is not a value of type “expr”? Choose one of the following answers:
A. Var “x”
B. App (Lambda “x” (Var “x”)) (Var “y”)
C. Lambda “x” (App (Lambda “x” (Var “x”)) (Var “y”)) D. App (Var “y”) (Var “x”)
E. Lambda ‘x’ (App (Var ‘x’) (Var ‘y’))
COMP3011 1
(b) Consider the following Miranda code:
f x y (Var x)
f x y (Var z)
f x y (App e1 e2)
f x y (Lambda x e1) = Lambda x e1
f x y (Lambda z e1) = Lambda z (f x y e1)
= App (f x y e1) (f x y e2)
(i) What is the type of the function “f”? Choose one of the following:
A. char -> char -> expr -> expr
B. (char, char, expr) -> expr
C. ([char], [char], expr) -> expr
D. [char] -> [char] -> expr -> expr
E. [char] -> [char] -> expr [char] -> expr [char] [4 marks]
(ii) What does the function “f” do? Choose one of the following answers:
A. It evaluates a lambda calculus expression
B. It performs variable substitution for a lambda calculus expression
C. It is the identity function for a lambda calculus expression
D. It removes free variable capture in a lambda calculus expression
E. Nothing because there is a code error [4 marks]
(iii) To what does the Miranda expression f “alpha” “beta” (Lambda “x” (App (Lambda “alpha” (Var “alpha”)) (Var “y”))) evaluate? Choose one of the following answers:
A. Lambda “x” (App (Lambda “alpha” (Var “alpha”)) (Var “y”))
B. Lambda “beta” (App (Lambda “alpha” (Var “alpha”)) (Var “y”))
C. Lambda “x” (App (Lambda “beta” (Var “beta”)) (Var “y”))
D. Lambda “x” (App (Lambda “beta” (Var “alpha”)) (Var “y”))
E. An error message because the expression has an error [5 marks]
COMP3011 2 Continued
(c) (i) What is a combinator? Choose one of the following answers:
A. A function with no free variables
B. A higher-order function
C. A function that combines the operation of two other functions D. An operator for algebraic types
E. A tag applied to the values of an algebraic type
(ii) Which of the following is the correct definition for the function commonly called “S” or “distribute”.? Choose one of the following answers:
A. distribute a b = a
B. distribute a b x = a x (b x) C. distribute x b a = b (a x) D. distribute a b c = (a . b) c E. distribute x = x
(ii) Consider the Miranda function definitions “g x y = x” and “h x y z = x z (y z)”. Which of the following partial applications is functionally equivalent
to the identity function “f” which is defined as “f x = x”? following answers:
Choose one of the
[7 marks] [Total 33 Marks]
A. B. C. D. E.
g h h h g g g h g g g h
2. (a) What operation does the following code perform (assuming the function is type-correct)?
f Empty = 0
f (Node x a b) = x + (f a) + (f b)
Choose one of the following answers (choose the most accurate answer):
(i) it resets to zero all the values in a data structure
(ii) it counts how many elements exist in a list
(iii) it adds all the values in a list of numbers
(iv) it sums all the values in a tree of numbers
(v) it counts the number of levels in a tree
(vi) it applies a function argument to all the values in a tree
(b) Which of the following are correct algebraic type definitions, and which are
incorrect? For each of (i) to (ix) say whether it is correct or incorrect: (i) dicevalues::=1|2|3|4|5|6
(ii) Fluid := Litres |Gallons
(iii) Fruit == Apples | Oranges
(iv) Tree :: Empty | Node x left right
(v) list ::= Nil | Cons * (list *)
(vi) cards ::= King | Queen | Jack | Other num
(vii) circle == Circle circle (viii) circle :: Circle circle
(ix) circle ::= Circle circle
COMP3011 4 Continued
(c) Given the following Miranda definitions, what does the expression (f test) return?
mytype * ** ::= Fred * | Mary [mytype ** *] test :: mytype num bool
test = Mary
f :: mytype
f (Fred x)
f (Mary [])
f (Mary [x])
f (Mary (x:xs)) = “{“++(f (Mary xs))++”}”
Choose one of the following answers (choose the most accurate answer): (i) 34
[ , Mary [Fred 34]]
num bool -> [char] = show x
(iii) “Mary [Fred 34]”
(iv) “[Fred 34]”
(v) “{(Mary [Fred 34])}”
(vi) “({Mary (Fred 34)})”
(vii) “{Mary []}”
= “(“++(show x)++”)”
(d) A recursive function called “rightmost” is required to take as input a value of type “(tree *)” as defined below and return the rightmost value stored in that tree.
tree * ::= Leaf * | BinaryNode * (tree *) (tree *) | MultiwayNode * [tree *]
(i) What would be the correct type for the function “rightmost” according to the specification? Choose one of the following answers:
A. tree -> num
B. tree -> [tree *] C. tree * -> [tree *] D. tree * -> *
[2 marks] (ii) The function “rightmost” uses pattern matching on its input argument.
COMP3011 5 Turn Over
Which of the following would NOT be a valid Miranda pattern for the input argument to this function? Choose one of the following answers:
A. (Leaf x)
B. (BinaryNode x y z) C. MultiwayNode x y D. x
E. (BinaryNode z x x)
(iii) Consider the Miranda expression rightmost (MultiwayNode 34 [Leaf 13, BinaryNode 17 (Leaf 14) (Leaf 18)]). What value should this return according to the specification? Choose one of the following answers:
B. (Leaf 13) C. 17
D. Leaf 14 E. 18
(iv) Consider the following code for the function “rightmost”, with numbered lines (the line numbers are not part of the code):
1. rightmost x =
getleaf x, if (isleaf x) xxrightmost x, if (isbinary xxxrightmost x, otherwise where
isleaf Leaf z
isleaf any
isbinary (BinaryNode x y z)
isbinary any
getleaf (Leaf z)
getleaf any
xxrightmost (BinaryNode x y z) = rightmost x xxxrightmost (MultiwayNode x []) = x
xxxrightmost (MultiwayNode x x) = rightmost (tl x)
Give the line numbers for all those lines that contain syntax or type errors, and say whether it is a syntax error or type error. For example, if you think that lines 1 and 2 contain syntax errors and line 2 also contains a type error, you should answer “LINE 1 SYNTAX, AND LINE 2 SYNTAX, AND LINE 2 TYPE”.
[10 marks] [Total 33 marks]
COMP3011 6 Continued
= error “non-leaf”
3. (a) Which of the following function definitions would be correct if the function
were specified to have the type num -> (num,num) -> bool ? function say whether it is correct or incorrect.
(i) fxy=True (ii) f (x,y) = False
(iii) f x (a,b) = (a=b) (iv) fx(a,b)=(=a)
(v) fxy=(x=y)
(b) What is the result calculated by the following program?
functions one, two and three are intended to represent, and give a more descriptive name for the function called “op”
one f x = f x
two f x = f (f x)
three f x = f (f (f x))
op a b f x = a f (b f x) main = op two one
(c) (i) What is the type of “g” defined below?
[10 marks]
g = (foldr (+) 0) . (foldr ((:) . ((#) . (:[]))) []) Choose one of the following answers:
G. [[*]] -> num
H. [num] -> [*]
I. (num -> num) -> ([*] -> num) -> num
(ii) What does the above function g do? Choose one of the following (choose the most accurate):
A. It returns the empty list
B. It returns the number 0
C. It adds the elements in a vector
D. It finds the number of rows in a list of lists of anything E. It returns the number of items in a list of anything
COMP3011 7 Turn Over
Suggest what the
(d) (i) What type would Miranda give to the following function?
f1 (a:b) f x = a ((x f b) . f)
Choose one of the following answers:
A. [(*->**)->***]->(*->****)->((*->****)->[(*->**)->***]->****->**)->*** B. [(num->num)->num->num]->[num->num]->num->num
C. [*] -> (num -> num) -> * -> *
D. [(*->**)->***]->(*->****)->(((*->**)->***)->num->****->**)->***
E. [*]->**->***->*
(ii) What type would Miranda give to the following function?
f2 [] y z = z f2 (a : b) y z
= (a z) & (f2 b y ((y . a . y) z))
Choose one of the following answers:
A. No type – the function definition has an error B. [num] -> (num->bool) -> num -> bool
C. [(num->num)->num->num]->[num->num]->num->num D. [bool->bool]->(bool->bool)->bool->bool
E. ([bool], bool, bool)->bool
COMP3011 8 Continued
[4 marks] [Total 33 marks] END OF PAPER
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com