What the heck is a function?

What is a function? Well, it’s a thing that takes things to things. That’s not very specific. But it turns out this very non-specific understanding is precisely what we need. Cast aside your preconceptions that functions have to return things that “behave well”, like integers or reals. They can return anything: even functions.

Why is this the case? Well, functions are things themselves. So they can be the input of another function or the output.

As an example, the derivative is certainly a function. It takes things to things. But its input is a function, and its output is too. Consider $f(x) = x^2$ and its derivative $f'(x) = 2x$ . Here we input the function $x^2$ and get an output of the function $2x$ .

A detour into set theory

OK, so functions are things. But mathematically, what are these things really? As with many other foundational questions, we must turn to set theory.

Say we have a function whose domain is $D$ and whose codomain is $R$ . Then a function $f$ is just a subset of $D\times R$ such that for every $x \in D$ , there is exactly one $y \in R$ such that $(x, y) \in f$ . We typically say $f(x) = y$ to denote that $(x, y) \in f$ .

OK, so functions are Cartesian products. Cartesian products are also sets, so there’s no reason you couldn’t take a Cartesian product of Cartesian products. The point here is, it should feel very mathematically natural to consider functions of functions.

There are many unquestioned assumptions here. What is an ordered pair $(x, y)$ ? It’s a set of the form $\{x, \{x, y\}\}$ . And what even is a set? Well… there’s a long answer involving naive set theory, Russel’s paradox, and ZFC… and really sets aren’t some intrinsic thing, they just are objects that satisfy some set of properties. Anyway, if you want to know more about this, I recommend Dr. Schimmerling’s A course in set theory (which I have gotten through a small chunk of). He also has notes on formal logic, which is necessary to fully understand the axioms of ZFC (i.e. what are properties, with respect to the comprehension scheme axiom?)

Functional programming

A slogan of of functional programming is that functions are values. In the beginning I wasn’t very specific with what a function is:

A function is a thing that takes things and returns things.

“Thing” is a little more well-defined in functional programming: roughly, we say any piece of data that doesn’t cause an exception/infinite loop/other flavor of disaster is a value. Integers are values, strings are values, booleans are values… and functions are values.

So let’s revise:

A function is a value that takes values and returns values.

Higher-order functions

But our naive functions, the ones that do basic things like take and return integers, are still useful to reason about. That’s why we have a special term for these functions that take functions: a higher-order function (HOF).

A higher-order function (HOF) is a function that either takes in functions or returns functions.

Okay, here’s an example of how higher order functions might help with a (made-up) case study. All code is written in Standard ML. You don’t really need to know SML to understand what is going on.

Suppose you want to have a function that allows Alice to input her favorite color to return a sentence that returns her favorite color.

fun aliceColor (color : string) : string =
    "Alice's favorite color is " ^ color

Note that the ^ operator performs string addition.

Now Bob wants in on the party. Okay, we’ll write him a function too.

fun bobColor (color : string) : string =
    "Bob's favorite color is " ^ color

Okay… seems a little redundant. I mean, it’s basically the same function as aliceColor.

And now Charles, Darla, Ethan, and Frank want in on the party. At this point, it might make sense to write a function that takes in a name and returns a function that allows people to express their favorite color. Let’s do just that!

fun colorQuery (name : string) : (string -> string) =
    (fn color => name ^ "'s favorite color is " ^ color)

If we write

val aliceColor = colorQuery "Alice"

then hooray, we have our function that allows Alice to input her own favorite color.

Currying

But what if I lied to you, the unassuming user, and told you that colorQuery took two inputs? Unless you messed around and found out, you’d believe me: colorQuery is a function that takes in a name and a favorite color, and says NAME’s favorite color is COLOR. But you, who has seen and analyzed the code for colorQuery, would go “no, you’re just applying functions twice.”

This is the same for our favorite functions. Consider the max function in Haskell. We switch to Haskell because in Haskell, every function is curried: that is, all functions secretly only take one input. This is not the case in SML. Open up ghci and type

max 4 5

You get 5, as you expect.

But now… try

max4 = max 4
max4 3
max4 5

Note max4 is a function value.

We get a function max4 that compares integers to 4 and returns the larger one.

Okay, let’s return to SML code, and write our own max function that is curried:

fun max (x : int) : (int -> int) =
    (fn y => if x < y then y else x)

If you ran

val bigger = max 4 5

then great, bigger is just 5. But if you run

val max4 = max 4

then the code evaluates to

val max4 =
    (fn y => if 4 < y then y else 4)

This shouldn’t be surprising: it’s how we defined the max function to begin with.

Currying functions like max isn’t very useful, but when you get to polymorphic higher-order functions, partial application can become very useful.

Conclusion

Here I presented several perspectives that all led to the same conclusion: functions can take in/spit out other functions. First consider the naive idea of a function as something that takes in things and outputs things. Well, functions are things. Then consider that functions are really subsets of Cartesian products, which are sets, so you can take a function (a subset of a Cartesian product) of a function (another subset of a Cartesian product, which is crucially a set!) Finally, consider that programatically, it is useful to return functions in order to remove redundant code. (That’s what Rust does for implementations of Traits!)

Maybe functions taking functions is old news to some of you. But hopefully a few of you came away with a new perspective on functions.