# Graph of a higher-order function

When we deal with functions which work on numbers, we can graph them easily: Just take each of its possible input values and find its corresponding point on one axis, then go straight up in its column, and there should be a point somewhere in the row corresponding to the resulting value of that function. (Or not, if the function is undefined for that particular argument. Multi-valued functions can also have more than one point in a column.)

But what about graphing higher-order functions (aka functionals or operators)?

For example, we can consider the differential operator $$\frac{d}{dx}$$ as being a (higher-order) function which works on other functions. That is, when supplied with a function, it finds (or maps it onto) another function. Give it the function $$y = x^3$$ and it will return its derivative, which is another function: $$y' = 3x^2$$. Give it $$y = x^2$$ and it will return $$y' = 2x$$. So we can make a table of these $$x$$s and $$y$$s to describe this mapping, as we could do with numbers:

• $$y = x^3 \;\;\longrightarrow\;\;y' = 3x^2$$
• $$y = x^2 \;\;\longrightarrow\;\;y' = 2x$$
• $$y = x \;\;\;\longrightarrow\;\;y' = 1$$

etc. The list can go in both direction, and actually we can even add some in-betweens because, for example, for the input $$y = x^{1/2}$$ there's an output as well: $$y' = \frac{1}{2x^{1/2}}$$. There's actually for any exponent $$n$$ we can think of, so we can arrange all the input functions on the horizontal axis, ordering them by $$n$$ – that is, we can put each $$y = x^n$$ at its corresponding $$n$$, and then put their corresponding derivatives on the vertical axis.

But then what about functions like $$y = x^3 + 7x - 1$$? There's no more room left on the horizontal axis! So the scheme with ordering these functions by $$n$$ won't work in this case. Even if we managed to put all polynomials on that axis somehow, there will still be functions like $$y = sin(x)$$ and much more...

But there certainly should be some way to graph them, since we can always map a point from one axis into a point on another. The problem is just this: where to put these points corresponding to certain functions in the first place? How should they be arranged/ordered? What does it mean for a function to be close to or far from some other function on that axis? What functions should lay next to each other?

For example, there's the identity function $$I$$ which is defined as $$x \rightarrow x$$, that is, maps every argument into itself. When the arguments are numbers, the graph will be a straight line. But what if the argument is a function? (It can be!) For example, when applied to the function $$y = x^2$$, it will return $$y = x^2$$ back (the same exact function). And in particular, when applied to itself, it will return itself: $$(x \rightarrow x) (x \rightarrow x)$$ results in $$(x \rightarrow x)$$, or symbolically, $$I(I) = I$$.

What would be the graph of the identity function? Well, my bet is that it should be a 2-dimensional graph, since we have one input variable and one output variable, so we need two axes. And I suppose the graph should be a straight line as well, as long as the positions of all these input & output functions are the same on each of the axes. And it won't depend on what order we put them on these axes, as long as the order is the same for both. The shape of the graph will be a straight line anyway.

But that's the thing: what should be the order of these rows & columns on the graph? How to find each of these possible functions's location on an axis?

Side note: Yup, I know about Lambda Calculus and its notation (I didn't use it here to make this question more accessible to people who don't know it). And this is precisely what brought me here: I'm looking for some way to depict these higher-order functions graphically.

There's, for example, a neat way for finding fixed points of "plain old" functions which work on numbers. Let's say we want to find a fixed point of the cosine function, so we write the fixed point equation:

$$x = \cos(x)$$

and now we just introduce a new symbol which is equal to each of the sides of this equation:

$$x = y = \cos(x)$$

and we can easily split it into a set of two equations which are functions:

$$\left\{\begin{array}{ll}y = x\\ y = \cos(x)\end{array}\right.$$

Now we just graph them and see where they cross each other, and the point where they cross is the fixed point of $$\cos$$.

But what when we're dealing with higher-order functions and $$x$$ is a function itself? It would be cool to be able to graph them somehow to see where they cross to find their fixed points (that is, to show what the $$Y$$ combinator from Lambda Calculus does). Or to show the mapping of the differential operator $$\frac{d}{dx}$$ from functions to their derivatives.

So my question is:

Are there some existing ways of graphing higher-order functions? What about ordering them on their axes? Is it possible to order all existing functions at all to put them on an axis of a graph? What if we limit ourselves to just computable functions? Does it make any difference?

Yes it makes a big difference. There are countably many programs, so you can number them using natural numbers. Similarly, each string can also be encoded as a unique natural number. You can hence plot of $F(x)$ against $x$ for every program $x$, given any function $F$ from programs to strings. You can do the same if $F$ is a program, but then the resulting graph will have 'holes' corresponding to where $F$ does not halt on the input.
You could use the above method to plot the graph of $Y(F)$ against $F$ for every program $F$, but that will not be very illuminating. If you attempt to follow the same idea of plotting $F(x)$ against $x$ to see where it 'intersects' the graph of the identity function, you still will not see the fixed-points of $F$. In fact, literally speaking there may not be any! The reason is that the fixed-point combinators do not produce literal fixed-points but only extensional fixed-points, where extensional equality (of a program) means "have the same output (or lack of it) on the same input". For example we have $Y(F) = ( x \mapsto F( t \mapsto x(x)(t) ) )( x \mapsto F( t \mapsto x(x)(t) ) )$, which can be proven to be extensionally equal to $F(Y(F))$, but they are not actually the same program.