I’ve already mentioned this to people here and there, but haven’t yet announced it publically, so here it is: Stephanie Weirich and I have been awarded a grant from the NSF to study the intersection of combinatorial species and (functional) programming, and so I’ll be returning the topic for my dissertation.
I’ve always found blogging to be an excellent way to organize my thoughts, and it often prompts great feedback and insights from readers which fuel further exploration. So as one aspect of my research, I plan to write a series of blog posts explaining the theory of combinatorial species and its relationship to algebraic data types. I’ll start with the very basics and (hopefully) progress to some deeper results, pulling together references to related things along the way.
I’ve written about species on this blog before (here, here, here, here, and here), and I published a paper in the 2010 Haskell Symposium on the topic, so I’ll certainly end up duplicating some of that content. But it’s worth starting over from the beginning, for several reasons:
- I want as many people as possible to be able to follow along, without having to tell them “first go back and read these blog posts from 2009”.
- I’m not completely happy with the way I presented some of that material in the past; in the intervening years I feel I’ve had some better insights into how everything fits together.
- Those previous posts—and my Haskell Symposium paper—conflated explaining species with explaining my Haskell library for computing with species,1 which I now think is not all that helpful, because it glosses over too many subtle issues with the relationship of species to algebraic data types.
So, in my next post, I’ll begin by defining species—but with some extra context and insight that I hope you’ll find enlightening, even if you already know the definition.
-
It’s on Hackage here, but I haven’t touched it in a long time and it doesn’t build with recent versions of GHC. I plan to fix that soon.↩
blog :: Brent -> [String] 
Awesome! Congratulations on the grant — looking forward to the new series on species!
+1
Congrats!
Very exciting, this is right up my ally.
Learn new math AND get some Haskelly insight, all in an ADD-friendly format? Sign me up!
Tremendously excited about this series. I may finally get around to doing my python port of your species library! Looking forward to it.
Pingback: Species definition clarification and exercises | blog :: Brent -> [String]
Pingback: The algebra of species: primitives | blog :: Brent -> [String]
http://www.nsf.gov/awardsearch/showAward?AWD_ID=1218002
Cool. Mirroring David’s comment I will probably end up porting portions of the species library to Ruby and C.
Stupid question, but how does your grant differ from what Sedgewick terms Analytic Combinatorics http://www.cs.princeton.edu/~rs/talks/FlajoletLegacy.pdf ?
To venture a guess I am envisioning something like Stepanov’s generics taken to a whole new level of specificity. The power of the abandoned C++0x Concepts determined in a lazy fashion.
It’s not a stupid question. A lot of the math underlying analytic combinatorics and species is the same. AC is all about doing analysis of algorithms, whereas our grant is more PL focused: how do we build programming languages using the theory of species as the underlying basis, and what do we gain by doing so? In other words, AC is about using the theory to analyze existing programs, whereas I want to program directly *in* the theory.