企业官网建设流程全解析

从生物学家那里取经，让 Haskell 编译更快

[2026 - 05 - 30]有人顺带提到，GHC 有个针对 `ApplicativeDo` 的标志（`-foptimal-applicative-do`），默认关闭，因其背后算法运行慢，无法投入使用。在作者看来，这像个漏洞，本以为花一个下午就能搞定这个因速度慢被禁用的优化，然而并非如此，这是个棘手问题，困扰了作者几个月。`ApplicativeDo` 是 GHC 较冷门功能，多数程序不启用，启用的大多也用默认设置，不用最优标志。但该标志背后问题值得研究，改进最优布局算法复杂度后，发现和生物学家预测 RNA 链折叠方式的动态规划方法一样。

什么是 ApplicativeDo，它为何如此强大？

以从远程社交图谱获取两人共同好友数量为例，展示标准 `do` 语法糖转换为顺序绑定的情况，这种执行是严格顺序的，需两次独立网络往返。而用 `Applicative` 实现，两次好友列表查询可变成一次数据库访问。手动编写 `<*>` 版本易出错，`ApplicativeDo` 允许开发者用普通 `do` 表示法，由编译器决定何时用 `<*>`。编译器要处理语句，确定依赖关系，独立语句用 `<*>` 组合，有依赖关系用 `>>=`。

最优调度的代价

组合独立语句不易，不同组合方式性能不同。通过代码块分析依赖关系，因 Haxl 会将 `<*>` 下计算批量处理成一次往返，所以关注总往返次数，往返越少延迟越低。GHC 默认算法用贪心策略，需四轮；最优方案并行处理，需三轮，节省一次往返。但最优算法时间复杂度是 `O(n³)`，最初论文中含 1000 条顺序语句的最坏情况 `do` 代码块，用最优算法编译需 55 秒，贪心启发式算法不到两秒，所以最优算法放在很少启用的标志后面。目标是不付出 `O(n³)` 代价得到最优结果。

问题简化

语句内容不重要，关键是依赖关系，可将语句建模为节点，用有向边表示依赖。编译器构建树，节点有顺序组合和并行组合，树的代价是所需轮数。要找到代价最小的合法树，论文发现复杂代码块只需检查两个极端分割点，除非结果相同，否则其中一个最优，工作量减到 `O(1)`。相同结果情况需进一步解决，论文将其作为开放性问题留下。

失败的启发式方法

一种直觉认为代价是最长依赖链，但实际并非如此，不允许重新排序会增加轮数，需真正的最小化搜索。另一种反转二维区间表的方法也被差异测试器证明错误，窗口内结构取决于两端，二维表是必要的。

限制搜索范围

病态输入是长链，无并行性，朴素算法为每个区间检查 `O(n)` 个分割点。出现相同结果时，若最长链等于 `c + 1`，搜索可终止。对于纯链，无需搜索就知代价，工作量从 `O(n³)` 减到 `O(n²)`。结合现有优化方法可减少工作量，但不能保证最坏情况是二次复杂度，密集代码块仍趋向立方复杂度，`hub` 行优化器扫描量和朴素算法一样。

与计算生物学的联系

RNA 链会自身配对形成二级结构，预测折叠是优化问题，用 Nussinov 算法解决。`ApplicativeDo` 代价函数与 RNA 折叠有相同的三角表、复杂度和递归关系。`do` 代码块与聚合物结构相同，编译器进行结构预测。RNA 二级结构预测和 `ApplicativeDo` 有共同约束，禁止键交叉和语句重新排序，嵌套结构将指数级搜索空间压缩成多项式级。允许键交叉或语句重新排序会使问题变成 NP 难问题。可借鉴生物学方法，顺序组合是 `(min, +)` 操作，`ApplicativeDo` 代价表受益于单调性引理。与解析建立联系，Bringmann 等人的算法实现亚立方时间。但该方法在编译器上下文中不太实用，前一节方法让最优算法在实际代码中快速运行，亚立方结果是关于问题的结论，非编译器实用方案。

结论

实际和理论解决方案基于每个区间并行性全有或全无的观察，可将代码块分割，限制昂贵搜索。`O(n³)` 复杂度影响编译时间，应用最长链界限和极端分割捷径可消除编译时间瓶颈，密集最坏情况与自然界计算机制有相似之处。