Department of Computer Science University College London
Cover Sheet for Examination Paper to be sat in May 2011
COMPGC16: Functional Programming
Time allowed 2.5 hours
Copyright By PowCoder代写 加微信 powcoder
Calculators are allowed Answer THREE questions
Checked by First Examiner: Date: Approved by External Examiner: Date:
COMPGC16: Functional Programming, 2011
Answer any THREE questions
Marks for each part of each question are indicated in square brackets. Calculators are permitted
1. Consider the following Miranda function definitions:
rc v g i = g (v:i) rn x = x
rh g = hd (g [])
f [] y = y
f (x:xs) y = f xs (rc x y)
g [] y = y
g (x:xs) y = g xs (x:y)
(a) What are the types of the functions rc, rn, rh, f and g?
(b) Evaluate the following expression by hand, giving all the intermediate steps:
rh (rc 1 (rc 2 (rc 3 rn)))
(c) What values do the following two expressions return?
(f [1,2,3] rn) [] g [1,2,3] []
[12 marks]
(d) Explain what the functions rc, rn and rh do, by comparing them with some other common Miranda functions or constructors.
[6 marks] [Total 33 marks]
COMPGC16 1 [Turn over]
(a) Given the following algebraic type definition for positive integers, give the type definitions and Miranda (or Amanda) code for two functions plus and times – the first of which will add two data items of type pos and the second of which will multiply two data items of type pos. In each case the function should return a value of type pos.
pos ::= Zero | Succ pos
[10 marks]
(b) Given the following function definitions which represent the first four positive integers as the function names one, two, three, and four, and assuming similar definitions for every positive integer, give the type definition and Miranda (or Amanda) code for a function called plus that will take as arguments two such functions representing integers and return as a result a function that represents the sum of the two input integers. For example, the application (plus one two) should evaluate to a function that takes two arguments (f and x) and returns the value (f (f (f x))).
one f x = f x
two f x = f (f x)
three f x = f (f (f x)) four f x = f (f (f (f x)))
[13 marks]
(c) Given the following two functions fnil and fcons, which respectively represent the empty list [] and the list constructor (:) as functions, give the Miranda (or Amanda) code for appropriate functions fhd and ftl which each take a functional representation of a list (i.e. either fnil, or fcons applied to two arguments) and return respectively the head of the input list or a functional representation of the tail of the input list. Do not attempt to provide the types for fhd and ftl. You may make use of the combinators cancel and swap in your answer – these functions are also defined below:
cancel x y = x swap f x y = f y x
fnil x = error “tried to take fhd or ftl of an empty list” fcons a b = f
where fg=gab
[10 marks] [Total 33 marks]
(a) What is the type of the following expression and what does it do? (The definitions
of the functions length and swap are given below).
(foldr (+) 0) . (foldr ((:) . length . (swap (:) [])) [])
length [] = 0
length (x:xs) = 1 + length xs swap f x y = f y x
(b) The following function foldiftrue folds only those elements of a list that satisfy a given predicate. Give the type definition for foldiftrue, and rewrite foldiftrue so that the function body uses the Miranda standard functions foldr and filter.
foldiftrue p f def [] = def foldiftrue p f def (x:xs)
= f x (foldiftrue p f def xs), if (p x) = foldiftrue p f def xs, otherwise
(c) Give the Miranda type definition for each of the following functions:
example1 a b f x = ( (a f) . (b f) ) x
example2 [] j acc = acc
example2 f [] acc = acc
example2 (x:xs) (y:ys) acc = example2 xs ys (x y acc)
example3 [] y z = 42.0 + z
example3 (x:xs) y z = example3 xs y ((x . y) z)
COMPGC16 3 [Turn over]
[13 marks]
[12 marks] [Total 33 marks]
(a) Give the Miranda (or Amanda) code and type definition for a function called shuffle that takes a number and a list of names and “shuffles” the names by interleaving them the number of times indicated by the first argument.
To interleave a list of names, the list should be cut into two halves and then put together by taking elements from each half alternately. If the list has an odd number of names, it does not matter where the final name ends up as long as it is retained in the output list. For example:
shuffle 1 [“Andy”, “Brian”, “Cate”, “Doris”, “Erica”, “Fred”]
shuffles the names once to give:
[“Doris”, “Andy”, “Erica”, “Brian”, “Fred”, “Cate”]
(b) Give the Miranda (or Amanda) code and type definition for a function called perms that takes a list of items and returns a list of lists giving all the different possible permutations of the input list. For example:
perms [1,2,3]
evaluates to
[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Note that the order in which the permutations appear is not important.
[18 marks]
[Total 33 marks]
COMPGC16 4 Continued
[15 marks]
(a) Give the grammar rules that define the syntax of a lambda calculus expression (with constants but without types) and state the operation of the three main evaluation (reduction) mechanisms.
(b) What is the Y combinator and why is it important? Show briefly (with diagrams) how the Y combinator may be implemented either using tree reduction or using graph reduction.
(c) Explain how a “free list” memory allocation algorithm operates. Give three different examples of sequential fit algorithms and compare their behaviour.
[13 marks]
(d) Explain how a “pointer increment” memory allocation algorithm might work together with sliding compaction to provide an automatic memory management system.
[10 marks] [Total 33 Marks]
[END OF PAPER]
COMPGC16 5 [Turn over]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com