Visiting assistant professor position at Hendrix

My department at Hendrix College is hiring a 1-year visitor in CS for next year. This is my third year at Hendrix and I really love it—the department is friendly and supportive, the administration really cares about faculty and students, and the students, on the whole, are motivated, bright, and enthusiastic. The position is a sabbatical replacement, so there’s no possibility of it turning into something longer than a year; nonetheless, it is a great opportunity for someone interested in pursuing a position at a liberal arts institution who wants to gain more teaching experience (something that is an absolute must for a liberal arts job but can be hard to come by in grad school). I think my department does a great job of supporting one another and helping each other grow as teachers, so it wouldn’t just be something to put on your CV, but a real opportunity to become a better teacher. And Conway, Arkansas is a wonderful place to live—despite what certain prejudices may lead you to believe!

The initial application deadline is soon (February 28)—I forgot to post something about it earlier!—but we’ll continue to accept applications until the position is filled, so don’t hesitate to apply even if you end up missing the deadline by a bit. And of course feel free to contact me with any questions.

Here’s a link to the application.

Posted in meta | Tagged , , , | Leave a comment

A (work in progress) translation of Joyal’s original paper on species

tl;dr: I’m working on an English translation, with additional commentary, of Joyal’s 1981 paper introducing the concept of combinatorial species. Collaboration and feedback welcome!

Back when I was writing my PhD thesis on combinatorial species, I was aware that André Joyal’s original papers introducing combinatorial species are written in French, which I don’t read. I figured this was no big deal, since there is plenty of secondary literature on species in English (most notably Bergeron et al., which, though originally written in French, has been translated into English by Margaret Readdy). But at some point I asked a question on MathOverflow to which I hadn’t been able to find an answer, and was told that the answer was already in one of Joyal’s original papers!

So I set out to try to read Joyal’s original papers in French (there are two in particular: Une théorie combinatoire des séries formelles, and Foncteurs analytiques et espèces de structures), and found out that it was actually possible since (a) they are mathematics papers, not high literature; (b) I already understand a lot of the mathematics; and (c) these days, there are many easily accessible digital tools to help with the task of translation.

However, although it was possible for me to read them, it was still hard work, and for someone without my background in combinatorics it would be very tough going—which is a shame since the papers are really very beautiful. So I decided to do something to help make the papers and their ideas more widely accessible. In particular, I’m making an English translation of the papers1—or at least of the first one, for now—interspersed with my own commentary to fill in more background, give additional examples, make connections to computation and type theory, or offer additional perspective. I hope it will be valuable to those in the English-speaking mathematics and computer science communities who want to learn more about species or gain more appreciation for a beautiful piece of mathematical history.

This is a long-term project, and not a high priority at the moment; I plan to work on it slowly but steadily. I’ve only worked on the first paper so far, and I’m at least far enough along that I’m not completely embarrassed to publicize it (but not much more than that). I decided to publicize my effort now, instead of waiting until I’m done, for several reasons: first, it may be a very long time before I’m really “done”, and some people may find it helpful or interesting before it gets to that point. Second, I would welcome collaboration, whether in the form of help with the translation itself, editing or extending the commentary, or simply offering feedback on early drafts or fixing typos. You can find an automatically updated PDF with the latest draft here, and the github repo is here. There are also simple instructions for compiling the paper yourself (using stack) should you want to do that.

  1. And yes, I checked carefully, and this is explicitly allowed by the copyright holder (Elsevier) as long as I put certain notices on the first page.

Posted in combinatorics, projects, species, writing | Tagged , , , , , , | 5 Comments

Off the Beaten Track: Explaining Type Errors

Last week I gave a talk at Off the Beaten Track 2018 about something that Richard Eisenberg, Harley Eades and I have been thinking about recently: namely, how to generate good interactive error explanations for programmers, especially for type errors. None of the talks at OBT were recorded, but I’ve prepared a version of my slides interspersed with (something like) a transcript of what I said.

Posted in projects, writing | Tagged , , , , , , , , | 2 Comments

Sum of heights in a binary tree

Executive summary: every year when teaching data structures I always forget how to analyze the cost of building a binary heap, which amounts to summing the heights of all the nodes in a full binary tree. So I’m writing down the (lovely) proof here in the hopes that I will remember it next time.

Suppose you have a full binary tree and you do an operation on every node, where the cost of the operation is proportional to the height of that node. That is, the cost for each of the n/2 leaves is 0, for each of the n/4 nodes in the next level up the cost is 1, and so on. We can visualize the scenario like this:

As a function of the total number of nodes n, how expensive is this? We can see that O(n \lg n) is an upper bound, since there are n nodes and the height of each node is at most \lg n. But it seems like it might actually be faster than this in reality, since, intuitively, most of the nodes have a height which is much smaller than \lg n.

(One specific motivation for this scenario is that we can build a binary heap from an arbitrary set of data by looping over the nodes from the bottom up and calling reheapDown on each; in the worst case reheapDown takes time proportional to the height of the node, as in this scenario. But it doesn’t matter if you don’t know about binary heaps.)

Let’s take the same tree and put a dollar at every node, for a total of \$n:

Now imagine sliding all the money as far up and to the right as it will go. That is, we take each dollar, and keep moving it up as long as it is a left child. As soon as we reach a node which is a right child we stop. The tree ends up looking like this:

Now take each pile of money and move it up one step to its parent, except the money at the root of the tree, which you can put in your pocket.

And voilà! We now have exactly enough money at each node to pay for the cost of the operations, and we even have a bit left over (which we can use to buy coffee). But we started with \$n and only shuffled money around; this shows that the total cost is actually O(n).

Exercise for the reader: what does this have to do with the number of bit flips needed to count from 1 to n with a binary counter?

Posted in math, teaching | Tagged , , , , , , , | 2 Comments

New baby, and Haskell Alphabet

My wife and I just had a baby!

If you missed seeing me at ICFP, this is why.

In honor of my son’s birth (he will need to learn the alphabet and Haskell soon)—and at the instigation of Kenny Foner—I revived the Haskell Alphabet by converting it to modern Hakyll and updating some of the broken or outdated links. Some of it is a bit outdated (I wrote it seven years ago), but it’s still a fun little piece of Haskell history. Enjoy!

Posted in haskell, meta | Tagged , , | 1 Comment

The Typeclassopedia is now up-to-date

The title pretty much says it all: I have finally finished (I hope) updating the Typeclassopedia to reflect various recent changes to the language and standard libraries (such as the AMP and BBP/FTP). Along the way I also added more links to related reading as well as more exercises.

How you can help

I am always on the lookout for more exercises to add and for more links to interesting further reading. If you know of a cool exercise or a cool paper or blog post that helps explain/illustrate/apply a standard Haskell type class, please let me know (or just add it yourself, it’s a wiki!). And, of course, the same goes if you notice any errors or confusing bits.

Happy Haskelling!

Posted in haskell, writing | Tagged , , , , | 10 Comments

Algorithms lecture notes and assignments

I just finished teaching our algorithms course for the second time. The first time around, last spring, I was always scrambling at the last minute to prepare for class, make new assignments, and so on (although I did have some excellent material from Brent Heeringa to start with). This time around, I had a bit more breathing room to develop a fuller set of assignments and actually TeX up all my hand-written lecture notes. The course is loosely based on the approach taken by Kleinberg and Tardos, though I don’t really rely on the book.

Feel free to use any of the lecture notes, assignments, or even exam questions. I didn’t leave the exams linked by accident; I use an exam format where the students have a week or so to prepare solutions to the exam, using any resources they want, and then have to come in on exam day and write down their solutions without referring to anything (I got this idea from Scott Weinstein). So leaving the exams posted publically on the web isn’t a problem for me.

Please don’t ask for solutions; I won’t give any, even if you are an instructor. But questions, comments, bug reports, etc. are most welcome.

Posted in teaching | Tagged , , , , , | 2 Comments