Derivatives of algebraic data structures: An excellent tutorial

Posted by Eric Kidd Fri, 20 May 2011 20:01:00 GMT

Last month, the folks at Lab49 explained how to compute the derivative of a data structure. This is a great example of how to write about mathematical subjects for a casual audience: They draw analogies to well-known programming languages, they follow a single, well-chosen thread of explanation, and there’s a clever payoff at the end.

The Lab49 blog post is, of course, based on two classic papers by Conor McBride, and Huet’s original paper The Zipper.

If you’re interested in real-world applications of this technique, there’s a great explanation in the final chapter of Learn You a Haskell for Great Good. If you’re interested in some deeper mathematical connections, see the discussion at Lambda the Ultimate.

Tags ,  | 5 comments

What do these fixed points have in common?

Posted by Eric Kidd Thu, 12 May 2011 12:09:00 GMT

A question asked while standing in the shower: What do all of the following have in common?

  1. Banach and Brouwer fixed points. If you’re in Manhattan, and you crumple up a map of Manhattan and place it on the ground, at least one point on your map will be exactly over the corresponding point on the ground. (This is true even if your map is larger than life.)
  2. The fixed points computed by the Y combinator, which is used to construct anonymous recursive functions in the lambda calculus.
  3. The Nash equilibrium, which is the stable equilibrium of a multi-player game (and one of the key ideas of economics). See also this lovely—if metaphorical—rant by Scott Aaronson.
  4. The eigenvectors of a matrix, which will still point in the same direction after multiplication by the matrix.

At what level of abstraction are all these important ideas really just the same idea? If we strip everything down to generalized abstract nonsense, is there a nice simple formulation that covers all of the above?

(I can’t play with this shiny toy today; I have to work.)

Tags ,  | 2 comments