Functional programming paradigm revision notes

Function type

A function f has a function type written f: A → B. Here, A is the domain, the set from which the function's input values are chosen, and B is the co-domain, the set from which the function's output values are chosen. Both are subsets of objects in some data type. A function assigns an output in the co-domain to each element in its domain, but it does not have to use every member of the co-domain.

For example, f: {a,b,c,…z} → {0,1,2,…,25} can map a to 0, b to 1, and so on. In this example, all values in the stated co-domain are used, although this is not required in general.

Functions as first-class objects

A function is a first-class object in a functional programming language, and also in an imperative language that supports first-class objects of this kind. It can appear in an expression, be assigned to a variable, be passed as an argument to another function, and be returned by a function call. This is a key distinction between a function and a value that can only be used as an ordinary input or output.

Function application

Function application is the process of applying a function to particular arguments. For example, add(3,4) applies add to integer values 3 and 4. Although this is commonly described as a function taking two arguments, the type can be represented as integer × integer → integer: the function takes one argument that is a pair, such as (3,4), and produces an integer.

Partial function application

Partial application supplies arguments one at a time. A two-argument function can be viewed as having the type add: integer → (integer → integer). Applying add to 4 returns a new function. When that new function is applied to another integer, it adds 4 to that integer. The brackets may be omitted, giving add: integer → integer → integer. The function is therefore viewed as taking one argument after another and eventually returning an integer.

Composition

Composition combines two functions to create a new function. If f: A → B and g: B → C, then g ○ f has domain A and co-domain C. The notation means that f is applied first and g is applied to the result. If f(x) = x + 2 and g(y) = y³, then (g ○ f)(x) = (x + 2)³.

Common errors

• Do not confuse the domain with the co-domain: the domain supplies inputs, while the co-domain supplies possible outputs.
• Do not assume every co-domain member must be produced.
• Do not reverse composition: g ○ f means f first, then g.
• In partial application, the result after supplying one argument is a function, not necessarily the final integer result.
• Distinguish a pair such as (3,4) from two separate arguments when describing the function type integer × integer → integer.