(纯)函数式编程是否与"算法经典"对抗？

Question

经典算法书籍(TAOCP,CLR)(而不是经典算法书籍,如fxtbook)充满了命令式算法.对于其实现主要基于数组的算法而言,这是最明显的,例如组合生成(在算法中使用数组索引和数组值)或联合查找算法.

这些算法的最坏情况复杂性分析取决于数组访问是O(1).如果用array-ish持久性结构替换数组,例如Clojure,则数组访问不再是O(1),并且这些算法的复杂性分析不再有效.

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

Answer 1

在数据结构方面,Chris Okasaki已经对将经典数据结构应用于纯功能设置进行了大量研究,因为许多标准数据结构在使用破坏性更新时不再有效.他的书"纯功能数据结构"展示了一些结构,如二项式堆和红/黑树,如何在功能设置中很好地实现,而其他基本结构如数组和队列必须用更精细的概念来实现.

如果你对追求核心算法的这个分支感兴趣,他的书将是一个很好的起点.

Answer 2

简短的回答是,只要算法没有完成后可以观察到的效果(除了它返回的效果),那么它就是纯粹的.即使您执行破坏性数组更新或突变等操作,这也会成立.

如果你有一个算法,比如说:

function zero(array):
    ix <- 0
    while(ix < length(array)):
       array[ix] <- 0
       ix <- ix+1
    return array

假设我们上面的伪代码词法范围,只要阵列参数首先复制和返回的数组是一个全新的东西,这个算法代表一个纯函数(在这种情况下,Haskell的功能fmap (const 0)可能会工作).书中显示的大多数"命令式"算法都是非常纯粹的功能,使用类似ST的东西在纯粹的功能设置中以这种方式编写它们是完美的.

我建议看看Mercury或Disciple Disciplined Compiler,看看仍然在破坏中茁壮成长的纯语言.

Answer 3

您可能对这个相关问题感兴趣：纯函数式编程的效率。

是否存在任何问题，最著名的非破坏性算法渐近地比最著名的破坏性算法更差，如果是的话，差多少？