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

Question

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

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

谢谢

Answer 1

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

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

对此的简单回答：涉及指针的事物。

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

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

• 由于指针构成了哈希表的基础，而且哈希表实际上只是实现了一个映射，因此已经全面研究了有效的功能映射。事实上，Chris Okasaki 有一本书（“Purely Functional Data Structures”）详细介绍了许多实现函数映射、双端队列等的方法......
• 由于指针可用于表示遍历某些较大数据结构内的节点，因此在这方面也有工作。该产品是zipper，一种高效的结构，简洁地代表了“更深结构内的指针”技术的功能等效。
• 由于指针可用于实现副作用计算，因此monad已被用来以一种漂亮的方式表达这种计算。因为跟踪状态很难处理，monad 的一个用途是让您掩盖程序中丑陋的命令式行为部分，并使用类型系统确保程序正确链接在一起（通过 monadic 绑定）。

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

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

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

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

Answer 2

请记住，大多数函数式语言都允许一些副作用的概念；它们可能不受欢迎，仅限于本地使用等，但您仍然可以使用它们。在 OCaml、Haskell、F#、Scala 或 Clojure 中，您可以根据需要使用可变数组。

因此，如果您发现一个算法，您有一个使用可变数组的公式，并且您需要用其中一种语言重现它，那么只需使用可变数组！

没有理由强迫自己使用单一的编程范式做所有事情；在某些问题领域，命令式编程（根据我们目前的知识）是最适合这项工作的工具，就像在某些领域逻辑编程非常出色一样。如果在本地封装使用这些范例之一可以节省您的时间和精力，那么您应该毫不犹豫地使用它们。

例如，Eratosthenes 的筛子用可变数组实现是微不足道的，并且很难以纯函数方式模仿（合理有效地）：有关详细信息，请参阅Melissa O'Neill文章。

另一方面，为给定问题找到不可变的解决方案可能是一项有趣且具有启发性的练习。Crhis Okasaki 的“Purely Functional Data Structures”一书是一个很好的例子，它以纯函数的方式对算法进行了非常好的重新表述。如果您对算法本身感兴趣（而不是它们对您的问题的应用），这可能是一个非常有趣的活动。

（有关使用共享来优化纯函数式算法的示例，请参阅 Richard Bird 和 Ralf Hinze 的 2003 年函数式明珠：共享的麻烦就是麻烦减半。）

Answer 3

可以以低渐近成本实现命令式功能，因此从抽象意义上讲，将命令式代码转换为纯函数式世界没有本质上的困难。在实践中，当然有。:-) 看看 Pippenger 的“Pure vs Impure Lisp”和引用它的论文。