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.

Advertisements
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

Submit to the Workshop on Type-Driven Development!

This year I am the co-chair (with Sam Lindley) of the Workshop on Type-Driven Development, affectionately known as TyDe1.

The workshop will be co-located with ICFP in Oxford, and is devoted to the use of “static type information…used effectively in the development of computer programs”, construed broadly (see the CFP for more specific examples of what is in scope). Last year’s workshop drew a relativey large crowd and had a lot of really great papers and talks, and I expect this year to be no different! Andrew Kennedy (Facebook UK) will also be giving an invited keynote talk.

Please consider submitting something! We are looking for both full papers as well as two-page extended abstracts reporting work in progress. The submission deadline for regular papers is 24 May, and 7 June for extended abstracts.


  1. Which I think (though I am not certain) that we decided is pronounced like “tidy”.

Posted in meta | Tagged , , , | 3 Comments

Deep work and email habits: a followup

About six months ago I wrote a post about some new work habits I adopted, inspired by Cal Newport’s blog and by his book, Deep Work. First, I began scheduling blocks of “deep work” time during the week, when I go to the library or a coffee shop and work intensely for several hours with no distractions or interruptions. Second, I decided to read and write email only after 4 pm each day. In my calendar, I put a reminder to write a followup blog post six months later, and here we are! (Has it been six months already!?)

My deep work sessions are still going strong, though having this opportunity to reflect has been good: I realized that over the months I have become more lax about using my computer and about what sort of things I am willing to do during my “deep work” sessions. It’s too easy to let them become just a block of time I can use to get done all the urgent things I think I need to get done. Of course, sometimes there are truly urgent things to get done, and having a big block of time to work on them can be great, especially if they require focused effort. But it pays to be more intentional about using the deep work blocks to work on big, long-term projects. The myriad little urgent things will get taken care of some other time, if they’re truly important (or maybe they won’t, if they’re not).

Since I’m only teaching two classes this semester, both of which I have taught before, I thought I would have more time for deep work sessions this semester than last, but for some reason it seems I have less. I’m not yet sure whether there’s something I could have done about that, or if the semester just looks different than I expected. This semester has also seen more unavoidable conflicts with my deep work blocks. Usually, I try to keep my scheduled deep work blocks sacrosanct, but I have made some exceptions this semester: for example, search committee meetings are quite important and also extremely difficult to schedule, so I let them be scheduled over top of my deep work blocks if necessary. (But it sure does wreak havoc on my work that week.)

I’m also still blocking my email before 4pm. On the one hand, I know this is helping a lot with my productivity and general level of anxiety. Recently I needed to (or thought I needed to!) briefly unblock my email during the day to check whether I had received a certain reply, and I specifically noticed how my anxiety level shot up as soon as I opened my inbox and saw all the messages there—a good reminder of why I have my email blocked in the first place. On the other hand, it can be frustrating, since the hour from 4-5 is often taken up with other things, so email gets pushed to the evening, or to the next day. When this goes on several days in a row it really doesn’t help my anxiety level to know there are emails sitting there that I ought to respond to. So perhaps there might be a better time to process my email than 4-5, but to be honest I am not sure what it would be. I certainly don’t want to do it first thing in the morning, and the middle of the day is not really any better, schedule-wise, than the end. In any case, I intend to keep doing it until a better idea comes along.

Posted in meta | Tagged , , | Leave a comment