Stealing from Biologists to Compile Haskell Faster(iankduncan.com)
iankduncan.com
Stealing from Biologists to Compile Haskell Faster
https://www.iankduncan.com/engineering/2026-05-30-stealing-from-biologists-to-compile-haskell-faster/
6 comments
Author here: yeah the end result is that you wouldn’t actually want to do it in practice. Who wants to build a load of linear algebra into GHC, after all? But it was pleasing to show that you could make the algorithm subcubic if you really wanted. to.
Those kinds of dependency chains look subject to a depth first search like Tarjan's strongly connected components algorithm, at least to my naive first pass reading. I've used it all over the place in e.g. analyzing foreign dependencies in database tables, or makefiles/rakefiles for task dependencies
It's always fun when someone asks an interview question that's even tangentially related and I get to go deep about the relative tradeoffs of a simpler algorithm like Tarjan's/Dijkstra's, over one of the more modern and faster but conceptually more challenging versions.
It's always fun when someone asks an interview question that's even tangentially related and I get to go deep about the relative tradeoffs of a simpler algorithm like Tarjan's/Dijkstra's, over one of the more modern and faster but conceptually more challenging versions.
This is monotone min-plus, so you can do it with even better running time than what you listed (which is just min-plus).
Also, if all numbers are at most k, you can even get running time related to k too, replacing n with k is obviously possible, but more can be done too. I feel this might be likely in practice where k might be small?
> GHC’s default algorithm works greedily: it grabs the longest run of independent statements from the front, emits it, and repeats.
I'm not sure I follow. If I had to write a greedy algoritm for this I would do a topological sort in O(n²) and then set the level of each expression to one bigger than the maximum level of its dependencies (again O(n²) worst case)
I'm not sure I follow. If I had to write a greedy algoritm for this I would do a topological sort in O(n²) and then set the level of each expression to one bigger than the maximum level of its dependencies (again O(n²) worst case)
So this can actually be implemented in GHC? I've only read through this once so far and not understood more than ¼, but the section right before the conclusion made it seem like the best you can do is O(n^2.82) along with a huge constant.