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.

Advertisements