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.

2 comments

2 Responses

Subscribe to comments with RSS.

sigfpe said, on 2014 August 12 at 8:31 am

I recognize that observation :-)
http://blog.sigfpe.com/2010/08/divided-differences-and-tomography-of.html

I think it’s pretty amazing that the same definition has these two entirely different interpretations.

You can go further. Both derivatives and divided differences of types can be seen as special cases of constraining types with regular expressions: http://blog.sigfpe.com/2010/08/constraining-types-with-regular.html

Reply
- Mike Stay said, on 2014 August 12 at 9:40 am
  
  That’s really cool!
  
  It looks like you were working with the case where h is not 0; as you noted, the single-step difference gives you the type of contexts with any number of holes, e.g. for f(x) = x³, Δf(x)/Δx = (f(x+1) – f(x))/(x+1 – x) = 3x² + 3x + 1. That is, there are three contexts with one hole, three with two holes, and one with three holes.
  
  The difference operator delta can actually be cast in terms of a q-derivative by taking q to be an operator on x rather than a ring element, e.g. q(x) = x+1. I asked John Baez about this yesterday and he told me that if F is any automorphism of a commutative algebra A over some field K, then for any k in K and a in A, we can define q(a) = k(F(a) – a). The result is something called a “twisted derivation”.
  
  Reply

reperiendi