哪些算法难以在函数式语言中实现？

Question

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

是否有人可以指向我的参考,这将有助于编写更难编写的算法(可能是那些通过共享状态优化的算法)？

谢谢

Answer 1

首先,正如您可能或可能不知道的那样,某些语言(包括Haskell)实现了共享,这可以缓解您可能想到的一些问题.

虽然安德鲁的回答指向了图灵的完整性,但它并没有真正回答在功能语言中难以实现哪些算法的问题.人们通常会问,在功能语言中难以实现哪些数据结构难以实现,而不是询问哪些算法难以在函数式语言中实现.

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

在向下钻取到机器级别时没有与指针相同的功能,有一个映射,您可以安全地将某些数据结构编译为数组或作为指针实现的内容,但在高级别,您可能无法表达事物在命令式语言中尽可能轻松地使用基于指针的数据结构.

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

• 由于指针构成了散列表的基础,并且由于散列表实际上只是实现了映射,所以已经全面地研究了有效的功能映射.实际上,Chris Okasaki有一本书("纯功能数据结构"),详细介绍了实现功能图,deques等的许多方法......
• 由于指针可用于表示某些较大数据结构遍历内的节点,因此该领域也有工作.该产品是拉链,一种有效的结构,简洁地代表了"更深层结构内部指针"技术的功能等同物.
• 由于指针可用于实现副作用计算,因此monad已被用于以非常方式表达这种计算.因为跟踪状态是很难兼顾的,monad的一个用途就是让你掩盖一个丑陋的命令行为你的程序的一部分,并使用类型系统来确保程序被正确链接在一起(通过monadic绑定).

虽然我喜欢说任何算法可以从势在必行一个非常容易的功能一个翻译,这根本就不是这样.但是,我相信问题不是算法本身,而是它们操纵的数据结构,基于强制性的状态概念.您可以在本文中找到一长串功能数据结构.

所有这一切的另一面是,如果你开始使用更纯粹的功能风格,你的程序中的大部分复杂性都会下降,并且对大量命令式数据结构的许多需求会消失(例如,在命令式中使用指针的常见情况)语言是实现令人讨厌的设计模式,这通常转化为功能级别的多态和类型的巧妙使用.

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

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

Answer 2

请记住,大多数功能语言允许一些副作用的概念; 它们可能不受欢迎,仅限于当地使用等,但您仍然可以使用它们.在OCaml,Haskell,F#,Scala或Clojure中,如果需要,可以使用可变数组.

因此,如果您发现使用可变数组的算法,并且需要使用其中一种语言重现它,那么只需使用可变数组即可!

没有理由强迫自己使用单一的编程范式来做所有事情; 有一些问题领域,命令式编程(根据我们当前的知识)是最适合工作的工具,正如逻辑编程非常出色的领域一样.如果它为您节省了时间和精力来进行本地封装使用这些范例之一,那么您应该毫不犹豫地使用它们.

例如,Eratosthenes的Sieve对于使用可变数组实现是微不足道的,并且以纯粹的功能方式更难模仿(合理有效地):详情请参阅Melissa O'Neill的文章.

另一方面,找到给定问题的不可变解决方案可能是一个有趣和有启发性的练习.Crhis Okasaki的"Purely Functional Data Structures"这本书是一个很好的例子,以纯粹的功能方式非常好地重构算法.如果您对算法本身感兴趣(而不是对您的问题的应用),这可能是一个非常有趣的活动.

(有关使用共享来优化纯函数算法的示例,请参阅Richard Bird和Ralf Hinze的2003 功能珍珠:麻烦共享是麻烦减半.)