Function composition

Let us now investigate a simple and familiar method of building functions: composing two existing functions to obtain another. The function composition f o g denotes the function with the property that (f o g) (x) = f(g x). This form of composition is known as composition in functional order. Another form of composition defines g; f to be f o g. This is known as composition in diagrammatic order. This is found in mathematical notation but not in programming language notation. Standard ML has a semicolon operator but it does not behave as described above. In fact, for two functions g and f we have instead that g ; f is f.

Notice that function composition is associative, that is: f o (g o h) = (f o g) o h. The identity function is both a left and a right identity for composition; id o f = f o id = f. Notice also the following simple correspondence between function iteration and function composition.

fⁿ = f o f o ... o f     where f occurs n times.

Function composition in functional order is provided in Standard ML by the predefined operator ``o''--the letter O in lower case. If f and g are Standard ML functions then f o g is their composition. However, we will define a compose function which is identical to (op o).

val compose = fn (f, g) => fn x => f(g x);