Big data & functional programming – A-level Computer Science exam questions with mark scheme

1Core3 marks

Big data is often described using three characteristics. Name these three characteristics and describe each one. [3]

Volume: there is too much data to fit on (or be processed by) a single server/computer (allow: too much data to store or process with conventional/traditional database tools). Do not accept just ‘a lot of data’, which only restates the name. Name and description both needed for each mark(1)
Velocity: data is created/arrives or changes at high speed (e.g. streamed), so it must be processed/responded to quickly, within milliseconds to seconds (either the high rate of arrival/change or the need for a very fast response is enough with the name)(1)
Variety: data comes in many different forms, structured and unstructured (e.g. text, images, video, sensor readings). Ignore other characteristics such as veracity or value(1)
Answer: Volume (too large for a single server), velocity (arrives and must be processed very quickly), variety (many forms, structured and unstructured)
Examiner tip: Name each V and describe it without just restating the word: for volume say the data is too large to fit on a single server, not just ‘a lot of data’.

2Standard4 marks

Big data is often stored using the fact-based model rather than a relational database.

(a) Describe the fact-based model. [3]

(b) Give one reason why it is suited to big data. [1]

(a) Each fact records a single, atomic piece of information (it cannot be broken down further). For any one of the three (a) marks, allow: each fact is uniquely identifiable (so two otherwise identical facts can be told apart)(1)
(a) Each fact is timestamped with when it was recorded / became true (allow: a fact is always true, as it is true at its timestamp)(1)
(a) Facts are immutable: they are never changed or deleted; when something changes a new fact is added (allow: data is only ever appended)(1)
(b) Any one: facts are only ever added, never updated, so the data can be spread across many servers and processed in parallel without update conflicts; the full history is kept so data lost to errors can be recovered or queried at any past time; new kinds of fact can be added without changing a fixed schema(1)
Answer: (a) Data is stored as atomic facts, each timestamped, which are immutable (never updated or deleted, only added) (b) e.g. append-only facts are easy to distribute across many servers without update conflicts / full history kept
Examiner tip: Immutable means no update or delete; a changed address is a new fact.

3Standard4 marks

In the functional programming language shown, map applies a function to every list item, filter keeps items for which a function returns true, and foldl combines a list from the left using a function and a starting value.

Evaluate each expression. [4]

(i)   map (+3) [1, 4, 2]
(ii)  filter (>2) [1, 4, 2, 5]
(iii) foldl (+) 0 [1, 2, 3, 4]
(iv)  foldl (-) 0 [10, 4, 3]

(i) [4, 7, 5](1)
(ii) [4, 5](1)
(iii) 10(1)
(iv) −17 (((0 − 10) − 4) − 3)(1)
Answer: (i) [4,7,5] (ii) [4,5] (iii) 10 (iv) −17
Examiner tip: In (iv) the fold starts with 0 on the left: 0 − 10 first, not 10 − 4.

4Hard5 marks

Two functions are defined:

add x y = x + y
inc = add 1
double x = x * 2

(a) Explain what is meant by partial application, using inc as your example. [2]

(b) Evaluate (double . inc) 4, where . is function composition. [2]

(a) Partial application means calling a function with fewer arguments than it takes, fixing those arguments (add is given only the argument 1)(1)
(a) The result is a new function (inc) that takes the remaining argument, so inc 4 = add 1 4 (allow: add has type integer → (integer → integer), so add 1 returns a function integer → integer)(1)
(b) inc applied first: inc 4 = 5, then double 5(1)
(b) 10 (correct answer with no working scores both marks)(1)
(c) 9(1)
Answer: (a) add applied to one argument gives a new function (b) 10 (c) 9
Examiner tip: Composition applies the right-hand function first: (double . inc) means double (inc x).

5Hard5 marks

(a) Write a recursive function countEven that returns the number of even integers in a list. For example countEven [3, 8, 5, 2, 6] returns 3. You may use the function even, head, tail or pattern matching (x:xs). [4]

(b) State the value of head [3, 5, 8] and of tail [3, 5, 8]. [1]

(a) Base case: countEven [] = 0(1)
(a) Recursive call on the rest of the list (xs or tail) in both cases(1)
(a) Even head: 1 + countEven xs (allow x `mod` 2 == 0 or similar in place of even x)(1)
(a) Odd head: countEven xs (no 1 added) (allow if/then/else or guards in place of pattern-matching cases). A non-recursive answer such as length (filter even xs) scores max 1 for (a)(1)
(b) head = 3 and tail = [5, 8] (both needed; tail must be a list)(1)

Examiner tip: A recursive function needs a base case for the empty list or it never terminates.

6Standard4 marks

Explain why functional programming is well suited to processing big data. [4]

Functions are stateless / have no side effects: the same input always gives the same output (allow: pure functions / referential transparency)(1)
Data structures are immutable, so no process can change data another process is using (no shared state, no race conditions or locking)(1)
So the processing can be split across many processors/servers and run in parallel (distributed), which big data needs because it will not fit on one server(1)
Higher-order functions such as map, filter and fold/reduce can be applied to each part of the data independently and the results combined (allow: makes it easier to write correct, efficient distributed code)(1)
Answer: Functions have no side effects and data is immutable, so there is no shared state; the data can therefore be split across many servers and processed in parallel safely, using higher-order functions such as map and reduce on each part.
Examiner tip: Explain the link: no shared state is what makes parallel execution safe.

Still losing marks on this topic?

Book a free introductory session and we'll find exactly which step is costing you.

Book a free intro