Definition: a functional is simply a
higher-order function, that is,
a function which takes functions as input and/or returns them as
output.
Here is an example of a higher-order type:
.
In the olden days, people were skeptical that currying and functionals would ever be useful.
Here is currying type isomorphism, plus lambda expressions implementing the isomorphism in each direction:
Exercise 1 (currying): define
Ackerman's function.
Recursion at higher types allows more than primitive recursion on
concrete data like integers.
For example, Ackerman's function cannot be written directly using primitive
recursion on integers;
however, it can be written by iterating a function.
Here is an example of how this is done, using a more familiar function
which simply adds two numbers in unary notation:
Exercise 2 (currying): Note: this is the
key to Ackerman's function. Recursively,
Another example of functionals are the various notations for function composition:
Note the similarity to the semicolon in programming languages: first you perform the lefthand argument, and then the righthand argument on the result. The only sequencing that is available in a purely functional setting is the fact that a function consumes its input before producing its output. Thus, by composing two functions we are sequencing them.