{
"cells": [
{
"cell_type": "markdown",
"id": "3d16f4ff",
"metadata": {},
"source": [
"# Higher-Order Functions\n",
"\n",
"Consider these functions `double` and `square` on integers:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "08595a87",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val double : int -> int = \n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val square : int -> int = \n"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let double x = 2 * x\n",
"let square x = x * x"
]
},
{
"cell_type": "markdown",
"id": "0584cfd2",
"metadata": {},
"source": [
"Let's use these functions to write other functions that quadruple and raise a\n",
"number to the fourth power:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "f0e6f080",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val quad : int -> int = \n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val fourth : int -> int = \n"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let quad x = double (double x)\n",
"let fourth x = square (square x)"
]
},
{
"cell_type": "markdown",
"id": "a8af363e",
"metadata": {},
"source": [
"There is an obvious similarity between these two functions: what they do is\n",
"apply a given function twice to a value. By passing in the function to another\n",
"function `twice` as an argument, we can abstract this functionality:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "5bc5f58f",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val twice : ('a -> 'a) -> 'a -> 'a = \n"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let twice f x = f (f x)"
]
},
{
"cell_type": "markdown",
"id": "9505a122",
"metadata": {},
"source": [
"The function `twice` is higher-order: its input `f` is a function.\n",
"And—recalling that all OCaml functions really take only a single\n",
"argument—its output is technically `fun x -> f (f x)`, so `twice` returns\n",
"a function hence is also higher-order in that way.\n",
"\n",
"Using `twice`, we can implement `quad` and `fourth` in a uniform way:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "adeebc6e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val quad : int -> int = \n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val fourth : int -> int = \n"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let quad x = twice double x\n",
"let fourth x = twice square x"
]
},
{
"cell_type": "markdown",
"id": "1a227c80",
"metadata": {},
"source": [
"## The Abstraction Principle\n",
"\n",
"Above, we have exploited the structural similarity between `quad` and `fourth`\n",
"to save work. Admittedly, in this toy example it might not seem like much work.\n",
"But imagine that `twice` were actually some much more complicated function. Then\n",
"if someone comes up with a more efficient version of it, every function written\n",
"in terms of it (like `quad` and `fourth`) could benefit from that improvement in\n",
"efficiency, without needing to be recoded.\n",
"\n",
"Part of being an excellent programmer is recognizing such similarities and\n",
"*abstracting* them by creating functions (or other units of code) that implement\n",
"them. Bruce MacLennan names this the **Abstraction Principle** in his textbook\n",
"*Functional Programming: Theory and Practice* (1990). The Abstraction Principle\n",
"says to avoid requiring something to be stated more than once; instead, *factor\n",
"out* the recurring pattern. Higher-order functions enable such refactoring,\n",
"because they allow us to factor out functions and parameterize functions on\n",
"other functions.\n",
"\n",
"Besides `twice`, here are some more relatively simple examples, indebted also to\n",
"MacLennan:\n",
"\n",
"**Apply.** We can write a function that applies its first input to its second\n",
"input:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "db446f93",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val apply : ('a -> 'b) -> 'a -> 'b = \n"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let apply f x = f x"
]
},
{
"cell_type": "markdown",
"id": "80dda8e6",
"metadata": {},
"source": [
"Of course, writing `apply f` is a lot more work than just writing `f`.\n",
"\n",
"**Pipeline.** The pipeline operator, which we've previously seen, is a\n",
"higher-order function:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "53c89ceb",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val pipeline : 'a -> ('a -> 'b) -> 'b = \n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val ( |> ) : 'a -> ('a -> 'b) -> 'b = \n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val x : int = 10\n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let pipeline x f = f x\n",
"let (|>) = pipeline\n",
"let x = 5 |> double"
]
},
{
"cell_type": "markdown",
"id": "948fbaa4",
"metadata": {},
"source": [
"**Compose.** We can write a function that composes two other functions:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "bca01bf1",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = \n"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let compose f g x = f (g x)"
]
},
{
"cell_type": "markdown",
"id": "6b6c277a",
"metadata": {},
"source": [
"This function would let us create a new function that can be applied\n",
"many times, such as the following:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "c5b2b200",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val square_then_double : int -> int = \n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val x : int = 2\n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val y : int = 8\n"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let square_then_double = compose double square\n",
"let x = square_then_double 1\n",
"let y = square_then_double 2"
]
},
{
"cell_type": "markdown",
"id": "93c52652",
"metadata": {},
"source": [
"**Both.** We can write a function that applies two functions to the same\n",
"argument and returns a pair of the result:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "be5d906c",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val both : ('a -> 'b) -> ('a -> 'c) -> 'a -> 'b * 'c = \n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val ds : int -> int * int = \n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"val p : int * int = (6, 9)\n"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let both f g x = (f x, g x)\n",
"let ds = both double square\n",
"let p = ds 3"
]
},
{
"cell_type": "markdown",
"id": "57be7032",
"metadata": {},
"source": [
"**Cond.** We can write a function that conditionally chooses which of two\n",
"functions to apply based on a predicate:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "49baea42",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"val cond : ('a -> bool) -> ('a -> 'b) -> ('a -> 'b) -> 'a -> 'b = \n"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"let cond p f g x =\n",
" if p x then f x else g x"
]
},
{
"cell_type": "markdown",
"id": "5080e4fc",
"metadata": {},
"source": [
"## The Meaning of \"Higher Order\"\n",
"\n",
"The phrase \"higher order\" is used throughout logic and computer science, though\n",
"not necessarily with a precise or consistent meaning in all cases.\n",
"\n",
"In logic, *first-order quantification* refers primarily to the universal and\n",
"existential ($\\forall$ and $\\exists$) quantifiers. These let you quantify over\n",
"some *domain* of interest, such as the natural numbers. But for any given\n",
"quantification, say $\\forall x$, the variable being quantified represents an\n",
"individual element of that domain, say the natural number 42.\n",
"\n",
"*Second-order quantification* lets you do something strictly more powerful,\n",
"which is to quantify over *properties* of the domain. Properties are assertions\n",
"about individual elements, for example, that a natural number is even, or that\n",
"it is prime. In some logics we can equate properties with sets of individual,\n",
"for example the set of all even naturals. So second-order quantification is\n",
"often thought of as quantification over *sets*. You can also think of properties\n",
"as being functions that take in an element and return a Boolean indicating\n",
"whether the element satisfies the property; this is called the *characteristic\n",
"function* of the property.\n",
"\n",
"*Third-order* logic would allow quantification over properties of properties,\n",
"and *fourth-order* over properties of properties of properties, and so forth.\n",
"*Higher-order logic* refers to all these logics that are more powerful than\n",
"first-order logic; though one interesting result in this area is that all\n",
"higher-order logics can be expressed in second-order logic.\n",
"\n",
"In programming languages, *first-order functions* similarly refer to functions\n",
"that operate on individual data elements (e.g., strings, ints, records,\n",
"variants, etc.). Whereas *higher-order function* can operate on functions, much\n",
"like higher-order logics can quantify over over properties (which are like\n",
"functions).\n",
"\n",
"## Famous Higher-order Functions\n",
"\n",
"In the next few sections we'll dive into three of the most famous higher-order\n",
"functions: map, filter, and fold. These are functions that can be defined for\n",
"many data structures, including lists and trees. The basic idea of each is that:\n",
"\n",
"* *map* transforms elements,\n",
"* *filter* eliminates elements, and\n",
"* *fold* combines elements."
]
}
],
"metadata": {
"jupytext": {
"cell_metadata_filter": "-all",
"formats": "md:myst",
"text_representation": {
"extension": ".md",
"format_name": "myst",
"format_version": 0.13,
"jupytext_version": "1.10.3"
}
},
"kernelspec": {
"display_name": "OCaml",
"language": "OCaml",
"name": "ocaml-jupyter"
},
"language_info": {
"codemirror_mode": "text/x-ocaml",
"file_extension": ".ml",
"mimetype": "text/x-ocaml",
"name": "OCaml",
"nbconverter_exporter": null,
"pygments_lexer": "OCaml",
"version": "4.14.0"
},
"source_map": [
14,
20,
23,
28,
31,
37,
39,
48,
51,
76,
78,
83,
87,
90,
92,
95,
99,
103,
107,
111,
114
]
},
"nbformat": 4,
"nbformat_minor": 5
}