31

经典的算法书籍（TAOCP、CLR）（以及不那么经典的书籍，例如fxtbook）都充满了命令式算法。这对于其实现主要基于数组的算法最为明显，例如组合生成（在算法中同时使用数组索引和数组值）或联合查找算法。

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

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

4

4 回答 4

8

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

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

于 2011-08-02T05:29:57.503 回答
8

简短的回答是，只要算法在完成后没有可以观察到的效果（除了它返回的效果），那么它就是纯粹的。即使您执行破坏性数组更新或突变之类的操作，这仍然成立。

如果你有一个算法，比如：

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，以了解仍然在破坏中茁壮成长的纯语言。

于 2011-08-02T07:28:53.137 回答
2

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

是否存在最知名的非破坏性算法在渐近上比最知名的破坏性算法更差的问题，如果是这样，差多少？

于 2011-08-02T09:11:58.933 回答
0

它不是。但确实可以在许多书籍中看到看起来只能在命令式语言中使用的算法。主要原因是纯函数式编程长期以来一直受限于学术用途。然后，这些算法的作者强烈依赖命令式特性成为主流。现在，考虑两种广泛传播的算法：快速排序和归并排序。快速排序比归并排序更“势在必行”；它的优势之一就是到位。合并排序比快速排序（在某种程度上）更“纯粹”，因为它需要复制并保持其数据持久化。实际上，很多算法都可以在纯函数式编程中实现而不会损失太多效率。例如，著名的《龙之书》中的许多算法都是如此。

于 2011-08-02T00:31:33.173 回答