В GHC есть флаг -foptimal-applicative-do, который ищет оптимальное расписание для do-блоков. Он включён по умолчанию — потому что его алгоритм слишком медленный. Автор решил, что это баг, который можно починить за полдня. Оказалось — нет. Проблема тянулась месяцы и привела к неожиданному открытию: та же динамическая программа, которой биологи предсказывают сворачивание РНК.
ApplicativeDo позволяет компилятору автоматически заменять последовательные >>= на параллельные <*>, когда это возможно. Например, два запроса friendsOf друг от друга не зависят — их можно выполнить за один раунд вместо двух. Greedy-алгоритм по умолчанию просто берёт самую длинную независимую цепочку с начала, но это часто даёт лишние раунды. Оптимальное расписание требует настоящего поиска — и оригинальный алгоритм из статьи «Desugaring Haskell’s do-notation Into Applicative Operations» имел сложность O(n³). Для 1000 последовательных операторов компиляция занимала 55 секунд.
Автор нашёл два улучшения. Первое — «extreme-cut shortcut»: если блок «запутан» (tangled), достаточно проверить только два крайних разреза — отделить первый оператор или последний. Внутренние разрезы не могут быть дешевле, потому что функция стоимости монотонна. Второе — longest chain bound: если нижняя граница (длина самой длинной цепочки зависимостей) равна верхней, искать не нужно. На цепочках это устраняет поиск целиком, и сложность падает до O(n²). На реальных блоках число проверок сокращается на порядок. Единственный паттерн, где shortcut не помогает — «hub», когда все операторы зависят от одного финального. Но такие конструкции в коде редки.
Связь с биологией оказалась не случайной. Фолдинг РНК использует ту же рекуррентную формулу: сворачивание куска определяется парой внутренней и внешней структур. И там тоже запрещены пересечения (псевдоузлы) — как и в ApplicativeDo нельзя переставлять операторы. Nussinov (1978) — это тот же O(n³). В 2016 Bringmann et al. показали, что благодаря «bounded-difference» (соседние значения отличаются не более чем на 1) можно применить технику Валианта и получить субкубическое время Õ(n^2.8244). Но для компилятора это бесполезно: константы гигантские, реальные do-блоки такого размера не бывают.
Практическая починка оказалась простой: отрезная декомпозиция плюс longest chain tie-breaker. Она полностью устраняет «компиляционный обрыв» для типичного кода. А редкий плотный случай, который выживает, — та же математика, что и в природе.