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.
(**) 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:
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.
d f is the derivative of
f, also of type
Num a -> Num c (res.
And now we see why
Dual was made a type constructor this time around:
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
:*:, 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
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
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
Find their derivatives by:
Or, for lack of an implementation of
applyExpr, inline the lambdas:
You’ll find that you get the expected results.