当前位置：文江博客话题详情

（纯）函数式编程与“经典算法”对立吗？

发布于 2024-11-27 16:28:29 字数 296 浏览 8 评论 0原文

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

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

傲娇萝莉攻 2024-12-04 16:28:30

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

如果你有一个像这样的算法：

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，以了解在破坏中仍然蓬勃发展的纯语言。

The short answer is that, so long as the algorithm does not have effects that can be observed after it finishes (other than what it returns), then it is pure. This holds even when you do things like destructive array updates or mutation.

If you had an algorithm like say:

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

Assuming our pseudocode above is lexically scoped, so long as the array parameter is first copied over and the returned array is a wholly new thing, this algorithm represents a pure function (in this case, the Haskell function fmap (const 0) would probably work). Most "imperative" algorithms shown in books are really pure functions, and it is perfectly fine to write them that way in a purely functional setting using something like ST.

I would recommend looking at Mercury or the Disciple Disciplined Compiler to see pure languages that still thrive on destruction.

回复收藏 0 原文

酷到爆炸 2024-12-04 16:28:30

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

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

回复收藏 0 原文

稍尽春風 2024-12-04 16:28:30

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

回复收藏 0 原文