1 comments

  • &gt; 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.<p>So this can actually be implemented in GHC? I&#x27;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.
    • iand6751 day ago
      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.