Species: making analytic functors practical for functional programming

Jacques Carette and Gordon Uszkay

Abstract

Inspired by Joyal’s theory of species, we show how to add new type constructors and constructor combinators to the tool set of functional languages. We show that all the important properties of inductive types lift to this new setting. Species are analytic functors, representing a broader range of structures than regular functors. This includes structures such as bags, cycles and graphs. The theory is greatly inspired by combinatorics rather than type theory: this adds interesting new tools to bear, but also requires more work on our part to show that species form a good foundations for a theory of type constructors. The combinatorial tools provide a calculus for these structures which has strong links with classical analysis, via a functorial interpretation of generating series. Furthermore, we show how generic programming idioms also generalise to this richer setting. Once the theory is understood, various methods of implementation are relatively straightforward.

Paper

The (submitted) paper is available in PDF. All comments are very welcome! (carette AT mcmaster DOT ca)

The Haskell code that accompanies the paper will be posted here later, after it has been cleaned up some. Also forthcoming are some Maple worksheets using the combstruct package to show how the combinatorial parts as well as the automated test generation aspects work.