algorithm - (纯)函数式编程是否与 "algorithm classics"对抗？

Question

经典算法书籍(TAOCP、CLR)(以及不太经典的书籍，例如 fxtbook)充满了命令式 算法。这对于实现严重基于数组的算法最为明显，例如组合生成(算法中同时使用数组索引和数组值)或联合查找算法。

这些算法的最坏情况复杂性分析取决于数组访问为 O(1)。如果您将数组替换为类似数组的持久结构，例如 Clojure，则数组访问不再是 O(1)，并且这些算法的复杂性分析不再有效。

这让我想到以下问题:纯函数式编程是否与经典算法文献不兼容？

Answer 1

关于数据结构，Chris Okasaki 对将经典数据结构采用到纯函数设置中进行了大量研究，因为许多标准数据结构在使用破坏性更新时不再有效。他的书“纯函数式数据结构”展示了一些结构，如二项式堆和红/黑树，可以在函数式设置中很好地实现，而其他基本结构如数组和队列必须用更复杂的概念来实现。

如果您有兴趣研究核心算法的这个分支，他的书将是一个很好的起点。