Stealing from Biologists to Compile Haskell Faster

2 days ago

GHC has an ApplicativeDo flag (-foptimal-applicative-do) that optimizes Haskell's do notation by grouping independent statements with <*> to reduce latency, but its algorithm is disabled by default due to being too slow.
The algorithm aims to minimize round-trips in monadic computations by constructing a dependency graph and finding an optimal scheduling tree, which originally had O(n³) complexity, making compilation times impractical for large blocks.
Optimizations include using a greedy heuristic by default and an extreme-cut shortcut for non-tied spans, reducing work significantly by leveraging monotonicity and longest-chain bounds to avoid unnecessary searches.
The problem parallels RNA secondary structure prediction in computational biology, where nested dependencies and non-crossing bonds allow polynomial-time solutions, with connections to min-plus matrix multiplication and parsing algorithms.
Practical improvements involve bounding the search with dependency chain lengths, cutting compile-time overhead for common cases, while theoretical sub-cubic solutions exist but are impractical for compilers due to high constant factors.

Hasty Briefsbeta