4.12 Fundamentals of functional programming
4.12.1 Functional programming paradigm
4.12.1.1 Function type
Content 
Additional information 

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 codomain. Know that the domain and codomain 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 codomain is a set from which the function’s output values are chosen. Not all of the codomain’s members need to be outputs. 
4.12.1.2 Firstclass object
Content 
Additional information 

Know that a function is a firstclass 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. 
Firstclass objects (or values) are objects which may:

4.12.1.3 Function application
Content 
Additional information 

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). 
4.12.1.4 Partial function application
Content 
Additional information 

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. 
4.12.1.5 Composition of functions
Content 
Additional information 

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 codomain is C. If the domain and codomains of f and g are ℝ, and f(x) = (x + 2) and g(y) = y^{3}. Then g ○ f = (x + 2)^{3} f is applied first and then g is applied to the result returned by f. 
4.12.2 Writing functional programs
4.12.2.1 Functional language programs
Content 
Additional information 

Show experience of constructing simple programs in a functional programming language. 
The following is a list of functional programming languages that could be used:
Other languages with builtin support for programming in a functional paradigm as well as other paradigms are:

Higherorder functions. 
A function is higherorder 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 is the name of a higherorder function that applies a given function to each element of a list, returning a list of results. filter is the name of a higherorder 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 higherorder function which reduces a list of values to a single value by repeatedly applying a combining function to the list values. 
4.12.3 Lists in functional programming
4.12.3.1 List processing
Content 
Additional information 

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:
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. 