Maps

Introduction

Since I haven't said what "space" means, this is kind of meaningless. Once we encounter precise definitions of various types of spaces, they'll be accompanied by precise notions of "map". Still, I'm going to use the word "map" more than "function" because it's shorter and more evocative. Also, sets are one kind of space (with no additional structure), and in that case map does mean any function.

Terminology

The difference between codomain and range can be hard to appreciate at first. The domain and codomain are part of the "type" of $f,$ wheras the image might be something difficult to determine.

In terms of vibes, the notation $f: X \to Y$ is approximately equivalent to

f: (x: X) => Y;

A more accurate (though still imperfect) translation would be

f: Map<X, Y>;

This is because in math, two functions $f$ and $g$ are considered equal if

they have the same domain and codomain
they map each input to the same output: $f(x) = g(x)$ for all $x \in X$

The second point is an important difference between functions in math and functions in programming (which are really algorithms). For mathematical functions, there's no such thing as a "function body" or "runtime".

Some more terminology.

Exponential interpretation

When we introduced products of spaces, we saw that that concept was related to multiplication of numbers. Functions are also related to a numeric concept: exponentiation.

For example, say we have two balls which can be painted any of three colors, red, green, blue. We can represent the possibilities as functions from $\{B_1, B_2\}$ to $\{\red r,\green g,\blue b\},$ e.g.

\vcenter{\LARGE{\red\bullet}{\blue\bullet}} \quad\text{corresponds to}\quad f(B_1) = \red r, \quad f(B_2) = \blue b.

There are $9=3^2$ possibilities in total:

\Big\{ f\colon \{B_1,B_2\} \to \{\red r ,\green g, \blue b\} \Big\} = \LARGE \left\{\begin{matrix} \red\bullet\red\bullet & \green\bullet\red\bullet & \blue\bullet\red\bullet\\ \red\bullet\green\bullet & \green\bullet\green\bullet & \blue\bullet\green\bullet\\ \red\bullet\blue\bullet & \green\bullet\blue\bullet & \blue\bullet\blue\bullet \end{matrix}\right\}

In general, if $X$ and $Y$ are finite sets with $|X|$ and $|Y|$ elements respectively, then the number of functions from $X$ to $Y$ is $|Y|^{|X|}:$ there are $|Y|$ options where to send each $x \in X,$ and we can choose those values independently of one another.

This suggests defining $Y^X$ as the set of functions from $X$ to $Y,$ so that

|Y^X| = |Y|^{|X|}.

This is called the function set or mapping space from $X$ to $Y.$ Although this can be hard to think about, it's very powerful to go from thinking about

individual elements of $X$ and $Y,$ to
individual functions $f: X \to Y,$ to
considering all functions $X \to Y$ as a single object.

Another notation for the mapping space (more common in CS than in math) is $X \to Y,$ in which case the notation $f: X \to Y$ is literally a type declaration. In any case, the mapping space from $X$ to $Y$ is approximately equivalent to the type (x: X) => Y or Map<X, Y>.

I'll try to avoid using the concept of mapping space except when we have precise definitions of "space" and "map", since

the precise definition of "map" will affect what the actual elements of $Y^X$ are. For example,
$\begin{align*} f&\colon \R \to \R\\ f(x) &= x+1 \end{align*}$

is considered an affine map but not a linear map.

depending on the precise meaning of "space", it may be easy, difficult, or impossible to turn the set of maps $X \to Y$ into a "space".

Maps and products

Let's see how this interacts with the other way we've seen of combining spaces, namely products.

Repeated multiplication

When $x$ is a natural number ( $0,1,2,...)$ and $y$ is any number, the exponential $y^x$ is defined as repreated multiplication:

y^x = \underbrace{yy\dotsm y}_{x\text{ times}}

Something similar is true for function spaces. Recall that three-dimensional space $\R^3$ can be understood as the threefold product of $\R$ with itself,

\R^3 = \R \times \R \times \R.

We can also view $\R^3$ as the function space $\R^{\{0,1,2\}}.$ In code, this is saying that the types

[number, number, number];

and

{
  0: number;
  1: number;
  2: number;
}

are "equivalent".

Depending on your application, you might prefer to have types like

{
  x: number;
  y: number;
  z: number;
}

or

{
  height: number;
  width: number;
}

These can be encoded as the mapping spaces $\R^{\{\r x,\r y,\r z\}}$ and $\R^{\{\r{height},\r{width}\}}.$

Maps into a product

Let $X,$ $Y,$ and $Z$ be spaces. We can form the product $Y \times Z,$ and then ask what maps $f\colon X \to Y \times Z$ look like.

By definition, $f$ needs to send each element $x$ of $X$ to an element of $Y \times Z.$ An element of $Y \times Z$ is a pair $(y, z)$ with $y\in Y$ and $z\in Z.$ So can define maps $g: X \to Y$ and $h: X \to Z$ as the first and second components of $f:$

f(x) = (g(x), h(x))

In other words, a function from $X$ to $Y \times Z$ is equivalent to two separate functions $X \to Y$ and $X \to Z$ . In terms of mapping spaces, we can express this as

(Y \times Z)^X \qeq Y^X \times Z^X.

(I'll say more about $\qeq$ in a future post.) This parallels the identity for numbers

(yz)^x = y^x z^x.

Here's what this equivalence looks like in code:

/** Projection onto first factor */
const pr1 = <X, Y>([x, y]: [X, Y]): X => x;

/** Projection onto second factor */
const pr2 = <X, Y>([x, y]: [X, Y]): Y => y;

/** Convert a function into a product to a pair of functions **/
const split = <X, Y, Z>(f: (x: X) => [Y, Z]): [(x: X) => Y, (x: X) => Z] => [
  (x) => pr1(f(x)),
  (x) => pr2(f(x)),
];

/** Convert a pair of functions to a function into a product */
const combine =
  <X, Y, Z>(g: (x: X) => Y, h: (x: X) => Z): ((x: X) => [Y, Z]) =>
  (x) =>
    [g(x), h(x)];

Maps out of a product

What about maps out of a product? That is, for spaces $X,$ $Y,$ $Z,$ let's think about what maps $X \times Y \to Z$ look like.

These correspond to "functions of two variables": for example, the function

f(x, y) = x^2 + y^2

is a map $\R^2 \to \R.$

There is another way of encoding a function of two variables: for a fixed value of $x,$ we can get a function $f_x: Y \to Z$ by defining

f_x(y) = f(x, y)

For instance, if $f(x, y) = x^2 + y^2$ as above, then $f_2(y) = 4+y^2.$ This is saying that a function of two variables can also be expressed as a function from $X$ to the set of functions from $Y$ to $Z$ . Symbolically, this is

Z^{X\times Y} \qeq (Z^Y)^X

or

(X \times Y) \to Z \qeq X \to (Y \to Z)

This "lifts" the numeric identity

z^{xy} = (z^y)^x.

In programming, this equivalence is called "currying".

/** Convert a function of two variables into a function returning a function. */
const curry =
  <X, Y, Z>(f: ([x, y]: [X, Y]) => Z): ((x: X) => (y: Y) => Z) =>
  (x) =>
  (y) =>
    f([x, y]);

/** Convert a function returning a function to a function of two variables. */
const uncurry =
  <X, Y, Z>(f: (x: X) => (y: Y) => Z): (([x, y]: [X, Y]) => Z) =>
  ([x, y]) =>
    f(x)(y);

Coproducts

There's one more exponential identity remaining,

z^{x + y} = z^x z^y

To get an analogue of this for mapping spaces, we need the concept of the coproduct $X \amalg Y.$ I don't want to really get into this concept right now, but it corresponds to the union type X | Y. The relevant identity is

Z^{X\amalg Y} \qeq Z^X \times Z^Y

Or if you prefer, this is saying that the types Map<X | Y, Z> and [Map<X, Z>, Map<Y, Z>] are "equivalent".

Convince yourself of the above, and implement the conversion in code.

Maps

Introduction #

Terminology #

Exponential interpretation #

Maps and products #

Repeated multiplication #

Maps into a product #

Maps out of a product #

Coproducts #