algorithm - 哪些算法难以用函数式语言实现？

Question

我正在涉足函数式语言，我发现一些算法(尤其是那些使用动态编程的算法)更难编写，有时在最坏的情况下运行时效率更低。是否有一类算法在具有不可变变量和副作用的函数式语言中效率较低？

有没有人可以指点我的引用资料，这将有助于编写更难的算法(可能是那些通过共享状态优化的算法)？

谢谢

Answer 1

首先，您可能知道也可能不知道，包括 Haskell 在内的一些语言实现了共享，这缓解了您可能想到的一些问题。

虽然 Andrew 的回答指出了图灵完备性，但它并没有真正回答哪些算法难以在函数式语言中实现的问题。人们通常不会问哪些算法很难用函数式语言实现，而是会问哪些数据结构很难用函数式语言实现。

对此的简单回答:涉及指针的事情。

当您深入到机器级别时，没有与指针等效的功能，有一个映射，您可以将某些数据结构安全地编译为数组或实现为指针的东西，但在高层次上，您无法表达事物在命令式语言中尽可能轻松地使用基于指针的数据结构。

为了解决这个问题，已经做了很多事情:

由于指针构成了哈希表的基础，并且由于哈希表实际上只是实现了一个映射，因此已经全面研究了有效的功能映射。事实上，Chris Okasaki 有一本书(“Purely Functional Data Structures”)详细介绍了许多实现函数映射、双端队列等的方法...

由于指针可用于表示遍历某些较大数据结构内的节点，因此在这方面也有工作。该产品是 zipper ，一种高效的结构，简洁地代表了“更深结构内的指针”技术的功能等价物。

由于指针可用于实现副作用计算，因此 monad 已被用来以一种漂亮的方式表达这种计算。因为跟踪状态很难处理，monad 的一个用途是让您掩盖程序中丑陋的命令行为部分，并使用类型系统确保程序正确链接在一起(通过 monadic 绑定(bind))。

虽然我想说任何算法都可以很容易地从命令式算法转换为函数式算法，但事实并非如此。但是，我相当确信问题不在于算法本身，而在于它们操作的数据结构，基于命令式的状态概念。您可以在 this post. 中找到一长串功能数据结构。

所有这一切的另一面是，如果您开始使用更纯粹的函数式样式，程序中的大部分复杂性都会降低，并且对大量命令式数据结构的许多需求也会消失(例如，在命令式中非常普遍地使用指针)语言是为了实现令人讨厌的设计模式，这通常转化为在功能级别上巧妙地使用多态性和类型分类)。

编辑:我相信这个问题的本质涉及如何以功能方式表达计算。但是，应该注意的是，有一些方法可以以函数方式定义有状态计算。或者更确切地说，可以使用函数式技术来推理有状态计算。例如， Ynot项目使用参数化的 monad 执行此操作，其中有关堆的事实(以分离逻辑的形式)由 monadic 绑定(bind)跟踪。

顺便说一句，即使在 ML 中，我也不明白为什么动态编程这么难。看起来像动态编程问题，通常建立一些序列的集合来计算最终答案，可以通过函数的参数来累积构造的值，在某些情况下可能需要继续。使用尾递归，没有理由不能像命令式语言那样漂亮和高效。现在可以肯定，您可能会遇到这样的论点，即如果这些值是列表(例如)，我们可以将它们实现为数组，但为此，请参阅帖子的内容:-)