# Term for functions that map functions to other functions

For example, let's define the "swap" function $SW(f(x,y))$ as the function that maps $f(x,y) \rightarrow f(y,x)$. I can imagine there are many such functions that have been described. Is there any useful term for such a thing?

EDIT: I'd like to illuminate a particular problem I'm interested in.

I begin with a set of functions that operate on two real numbers. For the sake of simplicity of this example, I'll use only three. For te variables $x,y,z\in \mathbb{R}$:

$$ADD(x,y) = x + y$$ $$MUL(x,y) = x*y$$ $$z = \sin(x)$$

$\sin(x)$ is defined in the traditional way. I'm including it to make my point a bit more clear.

Let's now define an equation that uses only these functions. I'll use a specific example of:

$$x*(y + z) + sin(x) = f(x,y,z)$$

I'm now interested in making the following idea more precise and general:

Define a function EX(f) whose purpose is to distribute multiplication over addition. Then, when applied to $f$ above,

$$EX(f) = g(x,y,z) = x*y + x*z + sin(x)$$

In this case, $f$ and $g$ evaluate to the same value so we might claim that $f=g$ in the numeric sense. However, I would not say they are equal from the perspective of actually computing those values, since a different set of steps must be followed. It is the latter case I'm interested in studying further, in which numeric equality is different from evaluation equality.

I'm interested in defining functions like EX, and determining things like stationary functions. For example, $EX(g) = g$, so $g$ is "stationary" under EX.

Forgive any imprecision. I hope it was enough to explain the type of things I'm looking for.

• Look up covariant and contravariant functors. – enedil Aug 16 '18 at 13:45
• I used the swap function as a specific example, though. I'm interested in the general class of such functions. For instance, I'd also be interested in a function that turns all subtractions into divisions, just to make up a strange example. Is that still covered? I'm very new to category theory and can never tell when an abstract concept in it is actually what I mean in the first place... – Michael Stachowsky Aug 16 '18 at 13:47
• @enedil I don't think that functors are the appropriate tool here, though they map morphisms to mormphisms. You have to define a functor on objects before you may define it on morphisms. And functors have to be compatible with compositions... – Babelfish Aug 16 '18 at 13:52
• @MichaelStachowsky Can you make it more precise what sort of functions you want to map? Are there some properties that the maps should preserve? Your example above is very special, it's just the pre-composition with $sw\colon X \times X \to X\times X, (x,y)\mapsto (y,x)$ – Babelfish Aug 16 '18 at 13:54
• @Babelfish: I'll edit the post to include what I'm trying to play around with. It's a special example that would be nice to have a good term for, although if there is a more general theory I'd be happy to hear about it as well. Edit is forthcoming – Michael Stachowsky Aug 16 '18 at 13:56

What you are describing are transformations of expressions or syntax trees. Computer scientists have a lot to do with those things.

While mathematicians are ordinarily interested in "extrinsic" equality, where $$f = g$$ when $$\forall x. f(x) =g(x)$$, computer scientists may consider the definition of an "algorithm" that actually presents the value of $$f(x)$$ when given $$x$$, and an expression is certainly one reasonable way to define an algorithm. (Particularly, "functional" programming languages will let you define algorithms via expressions and actually run the resulting programs.) In your example, $$f$$ and $$\mathrm{ex}f$$ are extrinsically equal, but "intrinsically" distinct.

One approach is to say that $$E\,\Sigma$$ is some "tree" functor from a set of Latin letters $$\Sigma$$, and $$\mathrm{sw}: \Sigma \to \Sigma$$ is a one to one "relabelling" function on those letters, that may be "lifted" to that functor as $$E\,\mathrm{sw}: E\,\Sigma \to E\,\Sigma$$, while $$\mathrm{ex}: E\,\Sigma \to E\,\Sigma$$ is a more general transformation of trees.

What you are calling "stationary" is a "fixed point" of a function. These are also used extensively in computer science. For example, if you start with an expression $$x$$ and apply some number of $$log_a$$ and $$exp_b: x \mapsto b^x$$ to it, you will get a family of expressions, and a fixed point of such application is the infinite group generated by $$\{\log_a, \exp_b | a, b \in \mathbb{R} \}$$. In such way a "language" — a set of expressions — can be defined.

I am merely a student, so in the above there may be errors and omissions. For future study, one entry point is "Algebraic and Coalgebraic Methods in the Mathematics of Program Construction", edited by Roland Backhouse, Roy Crole and Jeremy Gibbons. Not for the faint of heart though.

The usual term for those "functions" is the term "operator". For example, the operator $T$ that "swap" coordinates is defined by $T(f) = g$ with $g(x,y) = f(y,x)$.

• If I understand it, and I most likely don't, operator theory extends linear operators only. Is there a more general version that allows for any operation on a function space? – Michael Stachowsky Aug 16 '18 at 13:49
• @Michael Stachowsky: operator theory extends linear operators only --- Not really, otherwise you wouldn't see the term "linear operator" virtually always used everywhere in functional analysis texts. For nonlinear operators (such as differentiation operators), see this google search. Also, you might be interested in the even higher level abstraction discussed in Is there a such thing as an operator of operators in mathematics? – Dave L. Renfro Nov 7 at 14:29