Branium and the Santa Monica Haskell Users Group were kind enough to give me a chance to present about automatic differentiation for an evening, a topic we’ve visited before. This gave me a chance to improve my existing implementation and even add symbolic differentiation capabilities.

You can find the source code on GitHub, but I’ll inline the interesting bits.

Dual is now a type constructor, rather than a concrete type. This lets us accomplish a neat trick, which I will point out below.

Implementation of (**) is split into three cases in order to fix the bug mentioned in my earlier post. The three cases correspond to the power rule (variable raised to a constant), the exponential function rule (constant raised to a variable), and a third unnamed rule for finding the derivative of a variable raised to a variable. We can derive this rule using logarithmic differentiation:

\begin{align*} y &= u^v \\ \ln y &= \ln u^v \\ \ln y &= v \ln u \\ \frac{d}{dx} \ln y &= \frac{d}{dx} v \ln u \\ \frac{y'}{y} &= v' \ln u + v \frac{u'}{u} \\ y' &= y \left( v' \ln u + v \frac{u'}{u} \right) \\ y' &= u^v \left( v' \ln u + v \frac{u'}{u} \right) \\ \end{align*}

We also found it necessary to add an Ord (Dual a) instance (when Ord a exists, of course) for some bookkeeping later on (I forget exactly where).

Now for the neat trick. Normally, if we have a function $$f$$ in hand, then you can think of differentiation as two different processes. In the first process, you can choose a specific input $$c$$ and ask for $$f’(c)$$, presumably some kind of concrete type. We carry out this process when we ask Haskell to evaluate f $Dual 5 1, for example. A more general process would be to pretend we chose a specific number (using, say, $$x$$ as a placeholder) and use the formalism to arrive at a formula for $$f’$$ (in terms of $$x$$). In Haskell, we pretend that we chose a number like this: \x -> f$ Dual x 1. This lambda is the derivative $$f’$$ of the original function $$f$$. Let’s write down this lambda expression so that we don’t forget it.

So now, if f is a Haskell function with type Num a -> Num c (res. Fractional/Floating), then d f is the derivative of f, also of type Num a -> Num c (res. Fractional/Floating).

And now we see why Dual was made a type constructor this time around: f and d f would both be stuck being boring Double -> Doubles if Dual were simply defined as data Dual = Dual Double Double.

There are some illustrative examples in the repo that you might want to check out, but those aside, it’s time for symbolic differentiation.

For symbolic differentiation, I literally copied portions of code from Benjamin Kovach’s “Abstract Nonsense” blog post, Symbolic Calculus in Haskell. Kovach defines a type Expr a for algebraic expressions that accept and produce values of type a (“accept” and “produce” in paper-pencil-land, not in Haskell).

(In practice, you’d want more than just :+: and :*:, but we’re only going to implement Num (Expr a) today.)

Where Kovach implements a function derivative :: (Num a) => Expr a -> Expr a which returns an Expr a for the derivative of the passed Expr a, we take a different approach: we will write a Num (Expr a) instance, which will allow us to leverage our existing automatic differentiation machinery.

Automatic differentiation doesn’t do anything to Expr as. It requires a Haskell function–something like Num a => a -> a. So, the last ingredient we need is a way to think of an Expr a as a Haskell function. We get this by writing a function that evaluates an Expr a at a given a. Kovach implements a nice one. I’m going to just take one on credit for now:

And that’s it, we now have symbolic differentiation! For example, consider the following Expr as.

Find their derivatives by:

Or, for lack of an implementation of applyExpr, inline the lambdas:

You’ll find that you get the expected results.