COMP0020A7PD Functional Programming
c++ 代写 | data structure代写 – 这是一个关于c++的题目, 主要考察了关于数据结构的内容,是一个比较经典的题目, 是比较典型的数据结构和c++等test方向
EXAMINATION FOR INTERNAL STUDENTS
MODULE CODE : COMP
ASSESSMENT : COMP0020A7PD
PATTERN
MODULE NAME : Functional Programming
LEVEL: : Postgraduate
Controlled-Condition exam: 2 Hours exam
You cannot submit your work after the date and time shown on
AssessmentUCL you must ensure to allow sufficient time to upload and
hand in your work
This paper is suitable for candidates who attended classes for this
module in the following academic year(s):
Year
2021/
Duration 2 hours
Additional time for converting handwritten
notes to PDF where applicable^10 minutes^
Upload window^20 minutes^
Total time 2 hours 30 minutes
Additional material
Special instructions
Exam paper word
count
TURN OVER
N/A
N/A
N/A
Functional Programming, COMP0020 (A6U, A7P) Late Summer Assessment Period, 2021-
Suitable for Cohorts: 2021/22, 2020/21, 2019/
Answer ALL THREE questions. Do not plagiarise: especially, do not work with others, do not copy from others, do not copy from books or the web, and do not copy from the module presentations, slides, or other module material. Your answers must be your own work, in your own words.
Your answers will be marked for quality, including quality of expression.
Marks for each part of each question are indicated in square brackets. Standard calculators are permitted.
COMP0020 1 TURN OVER
- a. What value does the following expression compute? last [(x2) + 1 | x <- [1..]; (x2) < 5000000] where last [] = error "last of empty list" last [x] = x last (x:xs) = last xs [6 marks]
b. Why will Miranda not allow the following function definition?
dumb x = (x x)
[6 marks]
c. Given the following function definitions, where number is the name of a type
synonym:
one :: number
one f x = f x
two :: number
two f x = f (f x)
three :: number
three f x = f (f (f x))
i. Give a definition for the type synonym number that matches the type that
Miranda would otherwise infer for the type of the function three.
[4 marks]
[Question 1 cont. on next page]
COMP0020 2 CONTINUED
[Question 1 cont.]
ii. What type would Miranda infer for the following function and, considering it
in the context of the other definitions given above such that they all collaborate
as a set of functions, how would you express that type more succinctly using
the type synonym number?
operator a b = h
where
h c x = a c (b c x)
[6 marks]
iii. Explain the operation of the function operator (in the context of the other
definitions given above) by giving the evaluation steps of a simple application.
Then explain in general terms what the function operator does (for example,
could it be given a more descriptive name?).
[6 marks]
[Total for Question 1: 28 marks]
COMP0020 3 TURN OVER
- a. Define a polymorphic algebraic type to represent a binary tree in which the nodes of the tree hold values of any type, where all nodes in the tree must hold values of the same type. [4 marks]
b. Define a function to determine the height of a tree represented using the type you
defined immediately above, where the height of a tree is the number of nodes along
the longest branch from the root to a leaf.
[6 marks]
c. Give a high-level explanation of what the following function does. Give an example
of how it would be applied and the result it would return:
f :: (* -> ** -> *) -> * -> [**] -> [*]
f op = g
where
g r = (r:). j
where
j [] = []
j (a:x) = g (op r a) x
[10 marks]
d. Write a function called myf that is similar to the function f defined immediately
above but whose third argument is a polymorphic binary tree, and whose result is a
polymorphic binary tree.
[8 marks]
[Total for Question 2: 28 marks]
COMP0020 4 CONTINUED
- The game of solitaire is played on a board with holes and pegs. The holes have the following formation:
OOO
OOO
OOOOOOO
OOOOOOO
OOOOOOO
OOO
OOO
The game starts with pegs in all holes except the central hole. During the game, a peg
may jump another peg by moving North, South, East or West, but not diagonally. A peg
may only jump another peg if there is an empty hole on the other side of the peg being
jumped over. The peg which has been jumped over is removed from the board. The aim
of the game is to use a succession of jumps to remove all the pegs from the board except
one, which must end up in the central hole.
Provide Miranda code (including type expressions and comments) to implement this
game, using an algebraic type to represent the board. Your main function should accept a
list of moves, each of which comprises a starting position for a peg that the player would
like to move and the direction (North, South, East or West) in which the player would
like the peg to be moved. The main function should print to the screen the final board
position after all moves have been made successfully, or should abort with an appropriate
error message if any move is invalid for any reason.
You should include type expressions for all functions and provide appropriate comments.
This is an open-ended programming challenge within the time available to make your
answer as complete and as elegant as possible.
An ideal answer will not exceed 800 words of comments and code.
[44 marks]
[Total for Question 3: 44 marks]