## 2014-07-04

### Multi-valued functions

$\newcommand{\r}{\rightarrow} \newcommand{\R}{\mathbb R} \newcommand{\d}{\mathbin{\cdot}}$In the last post, I mentioned that the integration function returns the set of all functions of which the argument is the derivative. To reïterate, $\int : (\R\r\R)\r\{\R\r\R\}$. There's nothing strange about a function returning a set of values, so everything's good so far.

What we need are ways of dealing with these results. The typeclass that helps us here is the monad. For our purposes, a monad $m$ is just an applicative functor with a suitable $\text{join} : m\ (m\ a)\r m\ a$ function. For sets, this function takes a set of sets, then concatenates the inner sets. For functions, we infer from the type $(r\r(r\r a))\r(r\r a)$, equivalently $(r\r r\r a)\r r\r a$, that $\text{join}\ f\ x = f\ x\ x$. The function monad isn't immediately relevant, but it's there.

Now we need to define some more multi-valued functions. The obvious candidates are roots. Superscript-operator pairs are defined by
\begin{aligned} {}_*^1x &{}= x \\ {}_*^nx &{}= x*{}_*^{1-n}x \end{aligned}for non-zero natural $n$. This, for some operators and arguments, can be extended to cover non-natural $n$, but should still return a value of the same type as $x$. Thus, these cannot be multi-valued functions. Instead, roots written with the radical symbol, which are not defined this way, can be defined as multi-valued functions in the obvious way.

It may be worth defining an $\text{inv}$ function which returns the set of all possible inverse functions, rather than just the simplest one (as ${}_\circ^{1-0}$ does, by the above logic). So $\int = \text{inv}\ D$ and $\sqrt{\large\iota} = \text{inv}\ {}_\d^2$.

We have some functions, so let's try something simple. We can work out $\sqrt[4]x$ by doing $\text{join}\ \sqrt{\sqrt x}$:
\begin{aligned} \sqrt[4]{16} &{}= \text{join}\ \sqrt{\sqrt{16}} \\ &{}= \text{join}\ \sqrt{\{4,4-0\}} \\ &{}= \text{join}\ \{\{2,2-0\},\{2\d i,2\d i-0\}\} \\ &{}= \{2,2-0,2\d i,2\d i-0\} \end{aligned}Notice that I used implicit mapping, but implicit joining isn't a thing. We could want a set of sets, and implicit joining would screw that up.

Oh, and here's a relevant Red Dwarf joke:
In answering the question “What is a monoid in the category of endofunctors?” – write bigger – there are various words that need to be defined. What is a category, what is one of endofunctors, why is it one of endofunctors, and why is it so frequently linked with monoids?

What the hell is a monoid?
And there concludes the worst monad tutorial ever.