Department of Computer Science University College London
Cover Sheet for Examination Paper to be sat in May 2008
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, 2008
Answer any THREE questions
Marks for each part of each question are indicated in square brackets. Calculators are permitted
Describe two common forms of recursive function definition (not including tail or mutual recursion), with examples.
What is a polymorphic type? Give an example function definition (with its type definition) for a function whose type contains two polymorphic type variables, which are additionally constrained to be the same type.
Given the following function definition:
bizarre f x = f x (f x)
Explain why this definition would produce a type error. [8 marks]
What is lazy evaluation? Give an example function definition and application, together with a step-by-step illustration of how the application is evaluated, to explain two benefits of lazy evaluation. [6 marks]
Give an algebraic type definition for a type numchar that can hold either a num or a char. Give the function definition (with its type definition) for a function mapnumonly that takes two arguments – a function f of type num->num and a list of numchar – and returns a list of numchar where all numeric elements in the list have been modified by the function f but the character elements remain unchanged. Thus, mapnumonly operates like Miranda’s built-in map function, but only on the numeric elements in a numchar list, leaving the non-numeric elements unchanged.
[7 marks] [Total 33 Marks]
COMPGC16 2 Continued
2. Consider the following extract from a Miranda program:
|| Quicksort program.
|| An unsorted list of numbers is sorted by
|| recursively subdividing the list.
qsort:: [num] -> [num]
qsort [] = []
qsort (x:xs) = (qsort left) ++ [x] ++ (qsort right)
left = filter (< x) xs
right = filter (>= x) xs
(a) Give Miranda’s response for each of the following three expressions assuming it is typed at the Miranda prompt:
qsort [3,2,1]
(hd . qsort) [1,2,3] qsort [qsort, qsort]
(b) Write a function isort, with types and comments, which implements insertion sort (where elements of an unsorted list are inserted, one at a time, into a sorted list). Your function should take an unsorted list of numbers and return a list of numbers sorted in ascending order.
[10 marks]
(c) Generalize isort to create a new curried function allsort, which can sort a list of items of any type and where the ordering function is passed as an extra parameter. Give both the type declaration and function definition of allsort.
[10 marks] (d) Use partial application to provided specialized versions of allsort:
i. To sort a list of 2-tuples in descending order. For this function (2,3) is considered less than (1,7), because (2+3) is less than (1+7).
ii. To sort into ascending order a list of items of type dice where dice is defined as:
dice ::= One |Two |Three |Four |Five |Six
[Total 33 marks]
3. You are given the following definitions:
member :: [*] -> * -> bool
member [] y = False
member (x:xs) y = (x=y) \/ (member xs y)
foldr :: (*->**->**)->**->[*]->** foldr f def [] = def
4 Continued
foldr f def (x:xs) =
foldl :: (** -> * -> foldl f acc [] = acc foldl f acc (x:xs) =
f x (foldr f def xs)
**) -> ** -> [*] -> ** foldl f (f acc x) xs
(a) Write your own version of the Miranda built-in function map, using foldr. You may also use any other functions (except map) that you think are necessary.
[10 marks]
(b) Write two new definitions for the function member, each of which has the same type ([*]->*->bool) and functionality as the original function member, the first using foldr and the second using foldl in the function body.
[15 marks]
(c) Compare and contrast your definitions from part (b), paying particular attention to their types and to the ability to interchange foldr and foldl.
[8 marks] [Total 33 marks]
(a) Give a Miranda algebraic type definition for a set of items that may be empty or contain items. The new type should be polymorphic and the definition should be recursive, so that the set may contain any number of items.
(b) Provide function definitions (including their type definitions) for the following functions that operate on the new set type. The functions must ensure that there are never any duplicate items in a set.
subtractset
takes an item and a set and returns True if the item is in the set
takes a function “f” (of type *->bool) and a set and returns a set containing only those items x for which f x returns True.
returns an empty set
adds an item to a set
removes an item from a set
returns the intersection of two sets
returns the union of two sets
returns all the items of a set, collected into a list
The intersect function should use the higher-order function filterset. Minor syntactic errors will not be penalised.
[27 marks] [Total 33 marks]
6 Continued
(a) What is a combinator and why are combinators important? Give the definitions of two combinators which form a computationally complete set, and show how they may be used to mimic the action of the Identity combinator given below:
[10 marks]
(b) Explain how a “free list” memory allocation algorithm operates. Give three different examples of sequential fit algorithms and compare their behaviour.
[13 marks]
(c) 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]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com