> By applying the longest-chain bound and the extreme-cut shortcut, the compile-time cliff in GHC’s optimal path can be effectively eliminated— and the dense worst case that survives is, satisfyingly, deeply mirrors nature’s own computational machinery.

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.

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?

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.

> 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)

[flagged]