A-level Computer Science₇₅₁₇

Know that a function, f, has a function type

f: A → B (where the type is A → B, A is the argument type, and B is the result type).

Know that A is called the domain and B is called the co-domain.

Know that the domain and co-domain are always subsets of objects in some data type.

Loosely speaking, a function is a rule that, for each element in some set A of inputs, assigns an output chosen from set B, but without necessarily using every member of B. For example,

f: {a,b,c,…z} → {0,1,2,…,25} could use the rule that maps a to 0, b to 1, and so on, using all values which are members of set B.

The domain is a set from which the function’s input values are chosen.

The co-domain is a set from which the function’s output values are chosen. Not all of the co-domain’s members need to be outputs.

Know that a function is a first-class object in functional programming languages and in imperative programming languages that support such objects. This means that it can be an argument to another function as well as the result of a function call.

• appear in expressions
• be assigned to a variable
• be assigned as arguments
• be returned in function calls.

Know that function application means a function applied to its arguments.

The process of giving particular inputs to a function is called function application , for example add(3,4) represents the application of the function add to integer arguments 3 and 4.

The type of the function is

f: integer x integer → integer

where integer x integer is the Cartesian product of the set integer with itself.

Although we would say that function f takes two arguments, in fact it takes only one argument, which is a pair, for example (3,4).

Know what is meant by partial function application for one, two and three argument functions and be able to use the notations shown opposite.

The function add takes two integers as arguments and gives an integer as a result. Viewed as follows in the partial function application scheme:

add: integer → (integer → integer)

add 4 returns a function which when applied to another integer adds 4 to that integer.

The brackets may be dropped so function add becomes add:

integer → integer → integer

The function add is now viewed as taking one argument after another and returning a result of data type integer .

Know what is meant by composition of functions.

The operation functional composition combines two functions to get a new function.

Given two functions

f: A → B

g: B → C

function g ○ f, called the composition of g and f , is a function whose domain is A and co-domain is C.

If the domain and co-domains of f and g are ℝ, and f(x) = (x + 2) and g(y) = y ³ . Then

g ○ f = (x + 2) ³

f is applied first and then g is applied to the result returned by f .

Show experience of constructing simple programs in a functional programming language.

The following is a list of functional programming languages that could be used:

• Haskell
• Standard ML
• Scheme
• Lisp.

Other languages with built-in support for programming in a functional paradigm as well as other paradigms are:

• Python
• F#
• C#
• Scala
• Java 8
• Delphi XE versions onwards
• VB.NET 2008 onwards.

Higher-order functions.

A function is higher-order if it takes a function as an argument or returns a function as a result, or does both.

Have experience of using the following in a functional programming language:

• map
• filter
• reduce or fold.

map is the name of a higher-order function that applies a given function to each element of a list, returning a list of results.

filter is the name of a higher-order function that processes a data structure, typically a list, in some order to produce a new data structure containing exactly those elements of the original data structure that match a given condition.

reduce or fold is the name of a higher-order function which reduces a list of values to a single value by repeatedly applying a combining function to the list values.

Be familiar with representing a list as a concatenation of a head and a tail.

Know that the head is an element of a list and the tail is a list.

Know that a list can be empty.

Describe and apply the following operations:

• return head of list
• return tail of list
• test for empty list
• return length of list
• construct an empty list
• prepend an item to a list
• append an item to a list.

Have experience writing programs for the list operations mentioned above in a functional programming language or in a language with support for the functional paradigm.

For example, in Haskell the list [4, 3, 5] can be written in the form head:tail where head is the first item in the list and tail is the remainder of the list. In the example, we have 4:[3, 5]. We call 4 the head of the list and [3, 5] the tail .

[] is the empty list .