August | 2014 | reperiendi

Q, Jokers, and Clowns

Posted in Uncategorized by Mike Stay on 2014 August 5

Conor McBride has a beautiful functional pearl, “Clowns to the Left of me, Jokers to the Right”, in which he discusses the idea of suspending the computation of a catamorphism. I just wanted to point out the relation of his work to the $q$ -derivative. Since Star Trek’s character Q is a trickster god like Loki, Anansi, or Coyote, $q$ -derivatives also fit nicely with McBride’s theme.

The usual definition of the derivative is

$\displaystyle\frac{df(x)}{dx} = \lim_{h \to 0} \frac{f(x + h) - f(x)}{(x + h) - x}.$

Instead of translating $x$ by an infinitesimal amount $h$ , we can scale $x$ by an infinitesimal amount $q$ ; these two definitions coincide in the limit:

$\displaystyle\frac{df(x)}{dx} = \lim_{q \to 1} \frac{f(qx) - f(x)}{qx - x}.$

However, when people talk about the $q$ -derivative, they usually mean the operator we get when we don’t take the limit and $q \ne 1$ . It should probably be called the “ $q$ -difference”, but we’ll see that the form of the difference is so special that it deserves the exceptional name.

The $q$ -derivative, as one would hope, behaves linearly:

$\begin{array}{rl} \displaystyle \frac{d_qf(x)}{d_qx} & \displaystyle = \frac{f(qx) - f(x)}{qx - x} \\ \\ \displaystyle \frac{d_q(f(x) + g(x))}{d_qx} & \displaystyle = \frac{(f(qx) + g(qx)) - (f(x) + g(x))}{qx - x} \\ & \displaystyle = \frac{(f(qx) - f(x)) + (g(qx)- g(x))}{qx - x} \\ & \displaystyle = \frac{d_qf(x)}{d_qx} + \frac{d_qg(x)}{d_qx}\end{array}$

Even better, the $q$ -derivative of a power of $x$ is separable into a coefficient that depends only on $q$ and a single smaller power of $x$ :

$\begin{array}{rl}\displaystyle \frac{d_q x^n}{d_qx} & \displaystyle = \frac{(qx)^n - x^n}{qx - x} \\ &\displaystyle = \frac{q^n - 1}{q - 1}\frac{x^n}{x} \\ &\displaystyle = [n]_q x^{n-1},\end{array}$

where

$\displaystyle [n]_q = \frac{q^n - 1}{q - 1} = 1 + q + \cdots + q^{n-1}.$

Clearly, as $q \to 1$ , $[n]_q \to n$ . Whereas $n$ counts the number of ways to insert a point into an ordered list of $n-1$ items, $[n]_q$ counts the number of ways to insert a linearly independent ray passing through the origin into an $(n-1)$ -dimensional vector space over a field with $q$ elements with a given ordered basis.

The $q$ -derivative even works when $q$ is an operator rather than a number. Polynomials work in any rig, so if $x$ is, say, a function instead of a number, $q$ could be the Fourier transform.

Let’s lift this to types. The derivative of a datatype is the type of its one-holed contexts, so we expect the $q$ -derivative to have a similar interpretation. When we take $Q$ and $X$ to be types, the $Q$ -derivative of a tuple $X^n$ is

$\displaystyle [n]_Q X^{n-1} = X^{n-1} + (QX)X^{n-2} + (QX)^2X^{n-3} + \cdots + (QX)^{n-1}.$

Each option factors into two parts: the ‘clowns’ are a power of $QX$ to the left of the hole, followed by the ‘jokers’, a power of $X$ after the hole. This type is the one we expect for the intermediate state when mapping a function $f\colon X \to Q\times X$ over the tuple; any function $g\colon X \to Q$ can be lifted to such a function $f(x) = (g(x), x)$ .

Similarly, the $Q$ -derivative of the list datatype $1/(1-X)$ is $1/(1-QX)(1-X)$ ; that is, the ‘clowns’ form the list of the outputs of type $Q \times X$ for the elements that have already been processed and the ‘jokers’ form the list of the elements yet to process.

When we abstract from thinking of $q$ as a number to thinking of it as an operator on ring elements, the corresponding action on types is to think of $Q$ as a functor. In this case, $QX$ is not a pair type, but rather a parametric type $Q[X]$ . One might, for example, consider mapping the function $f(x) = 1/x$ over a list of real numbers. The resulting outputs will be real except when the input is zero, so we’ll want to adjoin an undefined value. Taking $Q = Option$ , the $Q$ -derivative of $List[Int]$ is $List[Option[Int]]\times List[Int]$ , consisting of the list of values that have already been processed, followed by the list of values yet to process.