Functional Programming, COMP0020 (A6U, A7P)

Main Summer Exam Period

Suitable for Cohorts: 2019/20, 2018/19, 2017/18

This alternative assessment consists of TWO questions. Answer ALL QUESTIONS. Students

should submit typed answers where possible, though it is recognized that scanned handwritten

answers may be necessary for some students.

Marks for each part of each question are indicated in square brackets.

Standard calculators are permitted.

COMP0020 1 TURN OVER

Alternative assessment, 2019/20

1. Consider the following Miranda function definitions that represent natural numbers as

functions:

zero f x = x

one f x = f x

two f x = f (f x)

a. Give a Miranda definition for a function called “plus” that takes two functions rep-

resenting numbers and returns a function representation of the result of adding the

numbers. For example, the application “plus one one” should return a function that

acts exactly like the function “two”.

[3 marks]

b. Give a Miranda definition for a function called “times” that takes two functions rep-

resenting numbers and returns a function representation of the result of multiplying

the numbers. For example, the application “times one two” should return a function

that acts exactly like the function “two”.

[8 marks]

c. In the context of the above functions, explain what the following function does:

f9 n = g

where

g f x = n p q r

where

p g h = h (g f)

q u = x

r u = u

[5 marks]

[Total for Question 1: 16 marks]

COMP0020 2 CONTINUED

2. Consider the following problem: a man is taking a dog, a chicken and some grain to

market. The man must cross a river using a small boat that can take the man and at most

one item (either the dog, the chicken or the grain). The dog must never be left alone with

the chicken, and the chicken must never be left alone with the grain. The man must find a

sequence of trips in the boat (either travelling “to the market” or “away from the market”)

that successfully gets him, the dog, the chicken and the grain across the river.

You are asked to write Miranda code, including type definitions, as described below. You

are NOT expected to have access to the Miranda system and therefore you will not be

penalised for code with minor syntax or type errors. Your code will however otherwise

be marked on correctness, completeness, coherence, elegance, clarity, understandability,

brevity, and use of functional programming style. You must include instructive comments

in your code. An ideal answer will not exceed 1,200 words of comments and code.

Your code should effectively model the above problem, generate candidate solutions (each

being a possible sequence of trips), search candidate solutions and select a valid solution

where (i) the dog is not left alone with the chicken, (ii) the chicken is not left alone with

the grain, and (iii) the final position has the man, the dog, the chicken and the grain on

the far bank of the river.

[84 marks]

[Total for Question 2: 84 marks]

COMP0020/COMP3011/COMPGC16 3 END OF PAPER