Differentiation of higher-order types
A “one-hole context” is a data structure with one piece missing. Conor McBride pointed out that the derivative of a regular type is its type of one-hole contexts. When a data structure is assembled out of common functor combinators, a corresponding type of one-hole contexts can be derived mechanically by rules that mirror the standard derivative rules learned in beginning differential calculus.
I’ve been playing with functor combinators lately. I was delighted to find that the data-structure derivatives can be expressed directly using the standard functor combinators and type families.
The code in this blog post is taken from the Haskell library functor-combo.
See also the Haskell Wikibooks page on zippers, especially the section called “Differentiation of data types”.
I mean this post not as new research, but rather as a tidy, concrete presentation of some of Conor’s delightful insight.