This started when someone mentioned, mostly in passing, that GHC has a flag for ApplicativeDo ( -foptimal-applicative-do ) that’s switched off by default because the algorithm behind it is too slow to use. That sounded like a bug to me. An optimization that’s correct but disabled for being slow is the kind of thing you fix in an afternoon, I figured. It wasn’t; it turned out to be a properly hard problem, and the problem has been eating at me for months. ApplicativeDo is a quiet corner of GHC to start with. Most programs never switch it on, and most of the ones that do are fine with the default and never reach for the optimal flag, so we’re well into the weeds even by compiler-internals standards. But the problem under the flag is a good one , and chasing improvements to the algorithmic compexity for the optimal layout algorithm led somewhere I didn’t expect: the same dynamic program biologists use to predict how a strand of RNA folds. What is ApplicativeDo, and why is it cool?…