The functor `arrOf`

takes a contract for a set of elements and produces a contract for the set of lists of those elements. Concatenation of lists makes them into a monoid. Let Mon be the category of monoids and monoid homomorphisms; then we can say that `arrOf`

is a functor from Set to Mon.

There’s another functor from Mon to Set that simply forgets the monoidal structure: it takes an element of a monoid and produces an opaque wrapper with one method, unwrap. Let’s call it `setOf`

.

The contract `setOf(arrOf(x)): Set -> Set`

is for a wrapped array of `x`

‘s. Given any element `xVal`

, we can produce a value `wrap([xVal])`

that passes `setOf(arrOf(x))`

.

The contract `arrOf(setOf(m)): Mon -> Mon`

is for lists of wrapped elements of a monoid. Given any list like

`[wrap(mVal1), wrap(mVal2), wrap(mVal3)]`

passing this contract, we can get a monoid element passing `m`

by unwrapping each element and multiplying them all together.

The categories Set and Mon are not equivalent: `setOf ○ arrOf`

is not isomorphic to the identity since there’s no way to take an element like `wrap([xVal1, xVal2, xVal])`

that passes `setOf(arrOf(x))`

and produce an element passing the contract `x`

that doesn’t depend on `x`

.

However, `setOf`

and `arrOf`

are related in a special way: with a little thought, it’s easy to see that the set of monoid homomorphisms from `arrOf(x)`

to `y`

is isomorphic to the set of functions passing `hom(x, setOf(y))`

: a monoid homomorphism from `arrOf(x)`

is completely specified by saying what it does to each of the values that pass `x`

: you just map that function over the list and then multiply the results together.

Two functors and are **adjoint functors** if for all objects c in C and d in D,

In the example above, is the set of functions from the set c to the set c’, and is the set of monoid homomorphisms from the monoid d to the monoid d’.

Other examples of adjoint functors include

- PSet is the category of “pointed sets”—
*i.e.*sets with a special chosen element called the “point”—and functions between them that map the point of the domain to the point of the codomain. Here, is the set c plus an extra point, while forgets which element of d was the special one. - where is the category whose objects are natural numbers and there’s a morphism from to if Here, the floor function forgets the fractional part of
- where is the category of polynomials of degree and there’s a morphism from f to f’ if f is bounded above by f’. Here, the derivative operator forgets the constant term.
- In general, any “forgetful” functor R that forgets some structure has a left adjoint L, the “free” structure of that kind.
- where Set² is the category of pairs of sets and pairs of functions between them, and This is a categorification of the fact that in real numbers,
- This is a categorification of the fact that in real numbers,
- This is a categorification of the fact that in real numbers,
- where Sub is the category of sets and inclusions (
*i.e.*there’s a morphism if ) - Here Bool is the category with two objects F and T and an arrow from F to T—that is, there’s an arrow from one object to another if the one implies the other. is the set of subsets of and maps F to the empty set and T to

Adjoint functors turn up all over the place.

## Leave a Reply