And now, back to your regularly scheduled combinatorial species

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.

  1. 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.

Posted in combinatorics, math, writing | Tagged , | 10 Comments

FogBugz, Beeminder, and… pure functions in the cloud?

For a number of years now, I’ve used a free personal instance of FogBugz to track everything I have to do. At any given time I have somewhere between 50-150 open tickets representing things on my to-do list, and over the last four years I have processed around 4300 tickets. This has been immensely successful at reducing my stress and ensuring that I don’t forget about things. However, it’s been somewhat less successful at actually getting me to do stuff. It’s still all too easy to ignore the really important but intimidating tickets, or at times to simply ignore FogBugz altogether.

Just last week, I discovered Beeminder. I’ve only been using it a week, but early indications are that it just might turn out to be as revolutionary for my productivity as FogBugz was. The basic idea is that it turns long-term goals into short-term consequences. You set up arbitrary quantifiable goals, and Beeminder tracks your progress over time and takes your money if you get off track—but you get to set the amount, and in fact it’s completely free until the second time you fail at a particular goal. In fact I haven’t even pledged any money for any of my goals; just the threat of “losing” has been enough to motivate me so far. (In fact, I’m writing this blog post now because I made a goal to write two blog posts a week, and by golly, if I don’t write a new post by tomorrow I’m going to LOSE!)

So, two great tastes that taste great together, right? I could make Beeminder goal(s) to ensure that I close a certain number of tickets per week, or a certain number of high-priority tickets, or a certain number of tickets with a given tag, or whatever seems like it would be helpful. Beeminder has a nice API for entering data, and FogBugz comes with a “URL trigger” plugin which can automatically create GET or POST requests to some URL upon certain events (such as closing a ticket matching certain criteria). The URL trigger plugin lets you construct an arbitrary URL using a list of special variables which get filled in with values from the given ticket. So I can just trigger a POST to the Beeminder URL for entering a data point, and give it arguments indicating the timestamp of the ticket event and a comment with the name of the ticket.

No problem, right?

Well… almost. There’s just one tiny catch. You see, FogBugz outputs timestamps in the format YYYY-MM-DD HH:MM:SS… and Beeminder expects a number of seconds since the epoch. Argggh!

I want to just plug in a little function in the middle to do the conversion. But both the FogBugz and Beeminder APIs are running on remote servers that I have no direct control over. I’d have to somehow send the FogBugz POST to some other server that I do control, munge the data, and forward it on to Beeminder. But setting this up from scratch would be a lot of work, not to mention the expense of maintaining my own server.

Here’s what I really want: a website where I can somehow write my function in a little domain-specific language, and get a URL where I can point FogBugz, which would cause my function to run on the timestamp and the result forwarded appropriately to Beeminder. Of course there are issues to be worked out with security, DOS attacks, and so on, but it seems to me it should be possible in principle.

Does something like this already exist? If not, why not? (And how hard would it be to build one using all the great Haskell tools for web development out there? =) It seems to me that the ability to write “glue” code like this to sit in between various APIs is becoming quite important.

Posted in meta | Tagged , , , , , , , | 16 Comments

Creating documents with embedded diagrams

If you read my recent post about type algebra, you may have wondered how I got all those nice images in there. Surely creating the images and then inserting them into the post by hand would be rather tedious! Indeed, it would be, but that’s not what I did. I’m quite pleased to announce the release of several tools for making this sort of thing not only possible but even convenient.

Behind it all is the recently released diagrams-builder package. Diagrams backends such as diagrams-cairo give you a static way to render diagrams. diagrams-builder makes the process dynamic: it can take arbitrary snippets of Haskell code, merge them intelligently, and call out to hint to render a diagram represented by some Haskell expression.

As a specific application of diagrams-builder, I’ve released BlogLiterately-diagrams, a diagrams plugin for BlogLiterately. This is what I used to produce the type algebra post. The entire post was written in a single Markdown document, with inline diagrams code in specially marked code blocks. BlogLiterately-diagrams handles compiling those code blocks and replacing them with the generated images; BlogLiterately automatically uploads the images to the server. For example, including

```{.dia width='200'}
sq = square 1

foo 0 = sq
foo n = ((foo' ||| sq') === (sq' ||| foo')) # centerXY # scale 0.5
    foo'   = foo (n-1)
    sq'    = sq # fc (colors !! n)
    colors = [black, red, orange, yellow, green, blue]

dia = foo 5 # lw 0

in the middle of a post results in

being included in the generated HTML.

Another exciting thing to mention is the LaTeX package diagrams-latex.sty, included in the diagrams-builder distribution. It lets you embed diagrams in LaTeX documents in much the same way that BlogLiterately-diagrams lets you embed diagrams in blog posts. Just stick diagrams code between \begin{diagram} and \end{diagram} and compile the document with pdflatex --enable-write18. It probably needs more work to smooth out some rough edges, but it’s quite usable as it is—in fact, I’m currently using it to create the slides for my Haskell Symposium presentation in a few weeks.

Just to give a little perspective, this is essentially why I started building diagrams, over four years ago now—I wanted to produce some illustrations for a blog post, but was unsatisfied with the existing tools I found. With these tools, I can finally say that I’ve fully achieved my vision of four years ago—though don’t worry, my vision has grown much larger in the meantime!

Posted in diagrams, haskell, projects, writing | Tagged , , , , , , , , , | 11 Comments

BlogLiterately 0.5.2 release, with improved image uploading

Just a quick note to say that I’ve just released version 0.5.2 of BlogLiterately. (For more information about what it does, see what I’ve written about previous releases here and here, and the documentation.) The new version keeps track of which image files have been uploaded—and their corresponding URLs on the server—in a special dotfile, so it only uploads a given image once, even across multiple runs of BlogLiterately. This is quite convenient, since it means that one can simply leave the --upload-images flag on when uploading successive drafts of a post, and images will be uploaded only once and available to be viewed in the preview version of your post.

Posted in haskell, writing | Tagged , , | Leave a comment

Identifying outdated packages in cabal install plans

Every time I build a Haskell package—whether using cabal or cabal-dev, whether something from Hackage or a development version of my own package—I always do a --dry-run first, and inspect the install plan to make sure it looks reasonable. I’m sure I’m not the only person who does this (in fact, if you don’t do this, perhaps you should).

But what is meant by "reasonable"? Really, what I look for are versions of packages being installed which are not the latest versions available on Hackage. Sometimes this is fine, if the package I am installing, or one of its dependencies, legitimately can’t use the most cutting-edge version of some package. But sometimes it indicates a problem—the upper bound on some dependency needs to be updated. (Note that I’m not trying to get into the upper bounds vs. no upper bounds debate here; just stating facts.)

To help automate this process, I threw together a little tool that I’ve just uploaded to Hackage: highlight-versions. If you take an install plan generated by --dry-run (or any output containing package identifiers like foo-0.3.2) and pipe it through highlight-versions, it will highlight any packages that don’t correspond to the latest version on Hackage.

For example, suppose running cabal-dev install --dry-run generates the following output:

$ cabal-dev install --dry-run
Resolving dependencies...
In order, the following would be installed (use -v for more details):

This is a big wall of text, and nothing is obvious just from staring at it. But piping the output through highlight-versions gives us some helpful information:

$ cabal-dev install --dry-run | highlight-versions
Resolving dependencies...
In order, the following would be installed (use -v for more details):
split- (
transformers- (
cmdargs-0.9.7 (0.10)
mtl- (2.1.2)
diagrams-cairo-0.5.1 (

We can immediately see that there are newer versions of the split, transformers, cmdargs, and mtl packages (and precisely what those newer versions are). We can also see that the version of diagrams-cairo to be installed is newer than the version on Hackage (since this is a development version). These aren’t necessarily problems in and of themselves, but in my experience, if you don’t know why cabal or cabal-dev have chosen outdated versions of some packages, it’s probably worth investigating. (--dry-run -v3 can help here.) This is also useful when uploading new versions of packages, to make sure they work with the latest and greatest stuff on Hackage. In this case the problems are just because of some changes I made to the .cabal file for the purposes of this blog post, making some upper bounds too restrictive, but in general it could be due to other dependencies as well.

Posted in haskell | Tagged , , , , , | 7 Comments

Unordered tuples and type algebra

At Hac Phi a few weekends ago (which, by the way, was awesome), Dan Doel told me about a certain curiosity in type algebra, and we ended up working out a bunch more details together with Gershom Bazerman, Scott Walck, and probably a couple others I’m forgetting. I decided to write up what we discovered. I have no idea what (if any) of this is really novel, but it was new to me at least.

The Setup

I’ll assume you’re already familiar with the basic ideas of the algebra of types0 represents the void type, 1 represents the unit type, sum is tagged union, product is (ordered) pairing, and so on.

Given a type T, since product represents pairing, we can write T^n to represent ordered n-tuples of T values. Well, how about unordered n-tuples of T values? Since there are n! possible ways to order n values, it seems that perhaps we could somehow divide by n! to "quotient out" by the symmetries we want to disregard: T^n/n!.

If you’ve never seen this sort of thing before it is certainly not at all obvious that this makes any sense! But bear with me for a minute. At the very least, we can say that if this is to make sense we ought to be able to use these sorts of type expressions to calculate the number of inhabitants of a finite type. So, let’s try it. For now let’s take T = Bool = 2. I’ll draw the elements of Bool as and .

There are clearly four different ordered pairs of Bool:

T^n is supposed to represent ordered n-tuples of T, and indeed, 2^2 = 4. How about unordered pairs? Since we don’t care about the order I’ll just choose to canonically sort all the Ts to the front, followed by all the Fs. It’s not hard to see that there are three unordered pairs of Bool:

(To distinguish them from ordered tuples, I’ll draw unordered tuples as above, with the elements slightly separated and a gray circle drawn round them.)

However, when we substitute T = n = 2 into T^n/n!, we get not 3, but (2^2)/2 = 2. What gives?

The problem

The problem is that T^n/n! is only correct if all the values in the tuples are distinct. Then we overcount each unordered tuple by exactly a factor of n!—namely, all the n! many permutations of the tuple, each of which is distinct as an ordered tuple. However, when some of the tuples have repeated elements, there can be fewer than n! distinct ordered variants of a given unordered tuple. For example, the unordered tuple has only 3 (rather than 3! = 6) ordered variants, namely

because the two ‘s are identical.

(As a small aside, when working in the theory of combinatorial species one is concerned not with actual data structures but with data structure shapes full of distinct labels—and the fact that the labels are distinct means that T^n/n! is (in some sense) actually the correct way to talk about unordered tuples within the theory of species. More on this in another post, perhaps.)

If T^n/n! is not the correct expression for unordered tuples, what is? In fact, Dan started off this whole thing by telling me the answer to this question—but he didn’t understand why it is the answer; we then proceeded to figure it out. For the purposes of pedagogy I’ll reverse the process, working up from first principles to arrive at the answer.

Counting unordered tuples

The first order of business is to count unordered tuples. Given a set T, how many unordered n-tuples are there with elements drawn from T (where repetition is allowed)? Again, since the order doesn’t matter, we can canonically sort the elements of T with all copies of the first element first, then all copies of the second element, and so on. For example, here is an unordered 8-tuple with elements drawn from T = 4 = \{ , , , \}:

Now imagine placing "dividers" to indicate the places where changes to , changes to , and so on:

(Note how there are two dividers between the last and the first , indicating that there are no occurrences of .) In fact, given that the elements are canonically sorted, it is unnecessary to specify their actual identities:

So, we can see that unordered 8-tuples with elements from T = 4 correspond bijectively to such arrangements of eight dots and three dividers. In general, unordered n-tuples are in bijection with arrangements of n dots and |T|-1 dividers, and there are as many such arrangements as ways to choose the positions of the |T|-1 dividers from among the n+|T|-1 total objects, that is,

\displaystyle \binom{n+|T|-1}{|T|-1}

(As an aside, this is the same as asking for the number of ways to place n indistinguishable balls in |T| distinguishable boxes—the balls in box i indicate the multiplicity of element i in the unordered n-tuple. This is #4 in Gian-Carlo Rota’s "twelvefold way", and is discussed on page 15 of Richard Stanley’s Enumerative Combinatorics, Volume I. See also this blog post I wrote explaining this and related ideas).

So what?

And now for a little algebra:

\displaystyle \begin{array}{cl} & \displaystyle \binom{n+|T|-1}{|T|-1} \\ & \\ = & \displaystyle \frac{(n+|T|-1)!}{n!(|T|-1)!} \\ & \\ = & \displaystyle \frac{(n+|T|-1)(n+|T|-2) \cdots (|T|)}{n!} \\ & \\ = & \displaystyle \frac{|T|(|T|+1)(|T|+2) \cdots (|T| + n-1)}{n!}\end{array}

The expression on top of the fraction is known as a rising factorial and can be abbreviated |T|^{\overline{n}}. (In general, x^{\overline{n}} = x(x+1)(x+2) \dots (x+n-1), so 1^{\overline{n}} = n!.) In the end, we have discovered that the number of unordered n-tuples of T is |T|^{\overline{n}}/n!, which looks surprisingly similar to the naïve but incorrect T^n / n!. In fact, the similarity is no coincidence, and there are good reasons for using a notation for rising factorial similar to the notation for normal powers, as we shall soon see.

And indeed, the correct type expression for unordered n-tuples of values from T is T^{\overline{n}} / n! = T(T+1)(T+2) \dots (T+(n-1))/n!. This means that if we consider the set of ordered n-tuples where the first element is drawn from T, the second element from T plus some extra distinguished element, the third from T plus two extra elements, and so on, there will be exactly n! of them for every unordered n-tuple with elements drawn from T. (In fact, we would even expect there to be some nice function from these "extended n-tuples" to unordered n-tuples such that the preimage of every unordered n-tuple is a set of size exactly n!—just because combinatorics usually works out like that. Finding such a correspondence is left as an exercise for the reader.)

A detour

Before we get back to talking about T^{\overline{n}}/n!, a slight detour. Consider the variant type expression T^{\underline{n}}/n!, where x^{\underline{n}} = x(x-1)(x-2) \dots (x-n+1) is a falling factorial. What (if anything) does it represent?

Subtraction of types is problematic in general (without resorting to virtual species), but in this case we can interpret T(T-1)(T-2) \dots as an ordered n-tuple with no duplicate values. We can choose any element of T to go first, then any but the first element to go second, then any but the first two, and so on. This can in fact be made rigorous from the perspective of types, without involving virtual species—see Dan Piponi’s blog post on the subject.

Infinite sums and discrete calculus

And now for some fun. If we sum T^{\underline{n}}/n! over all n, it ought to represent the type of unordered tuples with distinct values of any length—that is, the type of sets over T.

\displaystyle S(T) = 1 + T + \frac{T^{\underline{2}}}{2!} + \frac{T^{\underline{3}}}{3!} + \dots

Can we find a more compact representation for S(T)?

Consider the forward difference operator \Delta, defined by

\displaystyle \Delta f(x) = f(x+1) - f(x)

This is a discrete analogue of the familiar (continuous) differentiation operator from calculus. (For a good introduction to discrete calculus, see Graham et al.‘s Concrete Mathematics, one of my favorite math/CS books ever. See also the Wikipedia page on finite differences.) For our purposes we simply note that

\displaystyle \Delta x^{\underline{n}} = n x^{\underline{n-1}}

(proving this is not hard, and is left as an exercise). This is what justifies the notation for falling factorial: it is in some sense a discrete analogue of exponentiation!

The reason to bring \Delta into the picture is that given the above identity for \Delta applied to falling factorials, it is not hard to see that S(T) is its own finite difference:

\displaystyle \Delta S(T) = S(T)

Expanding, we get S(T+1) - S(T) = S(T) and hence S(T+1) = 2 S(T). (Yes, I know, there’s that pesky subtraction of types again; in the time-honored tradition of combinatorics we’ll simply pretend it makes sense and trust there is a way to make it more formal!) Solving this recurrence together with the initial condition S(0) = 1 yields

\displaystyle S(T) = 2^T

which we can interpret as the space of functions from T to Bool—that is, the type of sets over T, just like it should be! (Note that replacing falling factorial with exponentiation yields something which is its own derivative, with a solution of e^T—which indeed represents the species of sets, though it’s harder to see what e has to do with anything.)

Enough with the detour. What if we sum over T^{\overline{n}}/n!?

\displaystyle M(T) = 1 + T + \frac{T^{\overline{2}}}{2!} + \frac{T^{\overline{3}}}{3!} + \dots

There’s a backward difference operator, \nabla f(x) = f(x) - f(x-1), with the property that

\displaystyle \nabla x^{\overline{n}} = n x^{\overline{n-1}}

Hence \nabla M(T) = M(T), i.e. M(T) - M(T-1) = M(T), but here I am a bit stuck. Trying to solve this in a similar manner as before yields M(T-1) = 0, which seems bogus. 0 is certainly not a solution, since M(0) = 1. I think in this case we are actually not justified in subtracting M(T) from both sides, though I’d be hard-pressed to explain exactly why.

Intuitively, M(T) ought to represent unordered tuples of T of any length—that is, the type of multisets over T. This is isomorphic to the space of functions T \to \mathbb{N}, specifying the multiplicity of each element. I claim that \mathbb{N}^T is in fact a solution to the above equation—though I don’t really know how to derive it (or even what it really means).

\displaystyle \begin{array}{cl} & \displaystyle \mathbb{N}^T - \mathbb{N}^{T-1} \\ & \\ \cong & \displaystyle \mathbb{N}^{T-1}(\mathbb{N} - 1) \\ & \\ \cong & \displaystyle \mathbb{N}^{T-1} \mathbb{N} \\ & \\ \cong & \displaystyle \mathbb{N}^T \end{array}

The middle step notes that if you take one element away from the natural numbers, you are left with something which is still isomorphic to the natural numbers. I believe the above can all be made perfectly rigorous, but this blog post is already much too long as it is.

Posted in combinatorics | Tagged , , , , | 7 Comments

Monads: Easy or Hard?

Executive summary: they are actually both (or neither). It is easy to learn their definition but hard to grasp the consequences. Or we might say they are easy to know and hard to understand (grok). It is vitally important for both teachers and learners to understand and make this distinction.


The plethora of monad tutorials (well-covered elsewhere) has been intimidating Haskell beginners for years. Beginners understandably assume that anything with over thirty wildly different tutorials must be very difficult to learn. Sadly, this attitude is a self-fulfilling prophecy: it is difficult to learn something which intimidates you, independently of its intrinsic difficulty.

Well-meaning members of the Haskell community have sometimes reacted by going to the other extreme, assuring beginners that monads are actually quite easy, and there’s no reason for all the hype. Unfortunately, this can backfire: if someone is really convinced that monads are easy, they are going to be in for a demoralizing shock.

Both attitudes, however, are wrong! The key is to reject the dualistic easy/hard distinction and replace it with something more nuanced.


Monads are not hard; they are not easy; so what are they? They are profound. By this I mean that they have very large implications relative to the size of their definition. Here are some examples of other things that are profound in the same sense:

  • Board games like checkers, chess, go, and hex. It takes only a few minutes to learn the rules of these games, yet knowing the rules and being a good player are completely different. The simple rules of these games have many nontrivial and nonobvious "emergent" properties—which, of course, is what makes the games so interesting.

  • The lambda calculus, and Turing machines. Explaining how these work takes all of 30 minutes. Studying the implications, of course, has spawned multiple fields of active research.

  • Algebraic theories like group theory or category theory. Anyone with only a basic mathematical background can be taught the axioms of a group or a category. But, of course, these particular sets of axioms give rise to incredibly rich structure.

Thankfully, monads (as they arise in Haskell) are much less profound than these examples! But I think the analogy is correct. Understanding the definition of monads is simple: a monad is any type m of kind * -> * which supports the operations

return :: a -> m a
(>>=)  :: m a -> (a -> m b) -> m b

subject to some laws. But to really grok all the consequences—common example instances and how they are implemented and used; the relationship to Functor, Applicative, and Monoid; the relationship to the alternative definition in terms of join; all the common combinators like sequence, mapM, (>=>), etc.; and, in the end, to get some sort of intuitive sense for what the monad abstraction is really like—all that takes a long time and a lot of hard work!

Implications for pedagogy

So what does this all mean, practically speaking?

If you are learning about monads: take heart! There is a simple, easily accessible foundation from which to get started, namely, the definition of the Monad type class. Study the Monad methods and their types—and come back to this basic foundation whenever you get confused. But also realize that to gain deep understanding will take hard work over a relatively long period of time.

If you are teaching others about monads: encourage those who are intimidated—but don’t go overboard. Keep directing students back to the fundamental definition, but also provide them with many opportunities to engage with examples. (There is something else important here—examples of implementing monads are on a very different level than examples of using them, and in my experience it’s vitally important that students are explicitly taught to think about the two levels and keep them separate—but that’s a subject for another post.)


There’s probably nothing here that hasn’t been said by someone somewhere before, and it seems rather obvious now that I have written it, but I really do think this perspective is sometimes missing from the discussion of pedagogy and Haskell. This perspective really crystallized for me as I was teaching an introductory Haskell course last spring.

Of course, this is much in the same vein as my previous post Abstraction, intuition, and the “monad tutorial fallacy”. I still believe what I wrote there, except for one thing: that post makes it seem like it is possible to have a sudden "aha!" moment where one goes from not understanding monads to understanding monads. I now realize this is wrong, just like no one suddenly goes from "not understanding chess" to "understanding chess". The learning process is simply discontinuous; learners often experience big, sudden jumps in comprehension, and it’s easy to interpret these jumps as going from "not understanding" to "understanding". Immediately after making such a jump, it’s easy to believe that one had no prior understanding at all (which is probably not true), and that there’s nothing more to understand (which is certainly not true).

As a final note, I’ve specifically discussed monads here, but of course everything I’ve said applies to many other concepts as well, such as Applicative, continuations, GADTs, iteratees/pipes/conduits, and so on. I’d love for this to spark more explicit, thoughtful discussion of pedagogy in the community, and not just around monads.

Posted in haskell, learning, teaching | Tagged , , , | 4 Comments