我正在尝试使用函数式语言，并发现有些算法（尤其是那些使用动态规划的算法）在编写时更难且有时最坏情况下的运行时间更低效。在使用不可变变量和无副作用的函数式语言中，是否存在一类较低效的算法？
同时，是否有参考资料可以帮助我编写更难的算法（也许是通过共享状态进行优化的算法）？
谢谢
在函数式编程语言中难以实现哪些算法？
28
- GTDev
2
2https://dev59.com/sXI-5IYBdhLWcg3wKE-x - Don Stewart
1尽管在函数式语言和命令式语言中尝试使用相同的算法通常会导致性能损失，但是当考虑解决同一实际问题的不同算法时，这种情况要少得多。如果您是经验丰富的命令式程序员，并且正在尝试学习函数式语言，那么您关于算法的所有经验都将偏向于适用于命令式环境的算法。 - Ben
3个回答
35
首先，你可能已经知道一些语言，包括 Haskell，实现了共享（sharing）机制，这缓解了你所考虑的某些问题。
虽然 Andrew 的答案提到了图灵完备性，但它并没有真正回答函数式语言中有哪些算法是难以实现的问题。人们通常不是问哪些算法在函数式语言中难以实现，而是问哪些数据结构在函数式语言中难以实现。
简单来说：那些涉及指针的东西就比较难实现。
在机器级别下，函数式编程没有指针的等价物，尽管你可以将某些数据结构安全地编译成数组或类似指针的东西，但从高层次来看，使用基于指针的数据结构表达事物不如命令式语言那么容易。
为了解决这个问题，已经做了很多工作：
虽然 Andrew 的答案提到了图灵完备性，但它并没有真正回答函数式语言中有哪些算法是难以实现的问题。人们通常不是问哪些算法在函数式语言中难以实现，而是问哪些数据结构在函数式语言中难以实现。
简单来说：那些涉及指针的东西就比较难实现。
在机器级别下，函数式编程没有指针的等价物，尽管你可以将某些数据结构安全地编译成数组或类似指针的东西，但从高层次来看，使用基于指针的数据结构表达事物不如命令式语言那么容易。
为了解决这个问题，已经做了很多工作：
- 由于指针是哈希表的基础，并且哈希表只是实现映射的一种方式，因此人们广泛研究了高效的函数式映射。事实上，Chris Okasaki 写了一本书（"Purely Functional Data Structures"），详细介绍了许多实现函数式映射、队列等的方法。
- 由于指针可以用来表示某个大型数据结构遍历中的节点，因此在这个领域也进行了许多工作。产物是 zipper，它是一种高效的结构，简洁地表示了“深层结构内部指针”的函数式等价物。
- 由于指针可以用于实现具有副作用的计算，monads 被用来以优美的方式表达这种计算。因为跟踪状态很难把握，所以 monad 的一个用途就是让你 隐藏掉 程序中的丑陋命令式部分，并使用类型系统确保程序正确地链接（通过单调绑定）。
虽然我想说任何算法都可以轻松地从命令式的转换为函数式的，但事实并非如此。然而，我相信问题不在于算法本身，而是它们操作的数据结构，这些数据结构基于命令式状态的概念。您可以在此文章中找到很长的函数数据结构列表。
与此相反，如果您开始使用更纯粹的函数式样式，则程序中的许多复杂性将降低，并且许多对重度命令式数据结构的需求将消失（例如，命令式语言中非常常见的指针用于实现恶劣的设计模式，这通常会转化为函数级别的多态和类型类的巧妙使用）。
编辑：我认为这个问题的本质涉及如何用函数式方式表达计算。然而，应该注意的是，有方法以函数式的方式定义有状态的计算。或者说，可以使用函数式技术来推理有状态的计算。例如，Ynot 项目使用参数化的单子，在其中通过单子绑定跟踪堆（以分离逻辑的形式表示）的事实。
顺便说一下，即使在ML中，我也不认为动态规划有那么难。动态规划问题通常通过参数来累积某个序列的构造值以计算最终答案，在某些情况下可能需要一个延续。使用尾递归，这与命令式语言一样美观高效。现在当然，您可能会遇到这样的论点：如果这些值是列表（例如），那么我们可以将它们作为数组在命令式上实现，但对于此，请参阅文章内容 ：-）
- Kristopher Micinski
1
3我已经在将算法翻译成函数式语言方面做了很多工作。可能我从未成功看到人们令人满意地实现Ukkonen的后缀树算法，但那是一项非常复杂的工作。 - Louis Wasserman
7
请记住，大多数函数式语言允许一些副作用的概念；它们可能会受到反对，限制在本地使用等，但你仍然可以使用它们。在OCaml、Haskell、F#、Scala或Clojure中，如果需要，可以使用可变数组。
因此，如果你找到一个算法，并且你有一个使用可变数组的表述，而你需要在其中一种这些语言中复现它，那么就使用可变数组吧！
没有必要强迫自己使用单一的编程范例；有些问题域，命令式编程（根据我们目前的知识）是最适合的工具，就像有些领域逻辑编程是优秀的一样。如果使用其中一种范式节省了你的时间和精力，你应该毫不犹豫地使用它们。
例如，Sieve of Eratosthenes使用可变数组实现很容易，而在纯函数式编程方式下（合理高效地）模拟它则更加困难：详情请参见Melissa O'Neill的文章。
另一方面，找到针对某个问题的不可变解决方案可能是一项有趣而启发性的练习。Chris Okasaki的书《纯函数数据结构》是很好的算法纯函数化改写的例子。如果您对算法本身感兴趣（而不是它们应用于您的问题），那么这可能是一项非常有趣的活动。
（有关使用共享优化纯函数算法的示例，请参见Richard Bird和Ralf Hinze的2003年Functional Pearl：Trouble Shared is Trouble Halved。）
因此，如果你找到一个算法，并且你有一个使用可变数组的表述，而你需要在其中一种这些语言中复现它，那么就使用可变数组吧！
没有必要强迫自己使用单一的编程范例；有些问题域，命令式编程（根据我们目前的知识）是最适合的工具，就像有些领域逻辑编程是优秀的一样。如果使用其中一种范式节省了你的时间和精力，你应该毫不犹豫地使用它们。
例如，Sieve of Eratosthenes使用可变数组实现很容易，而在纯函数式编程方式下（合理高效地）模拟它则更加困难：详情请参见Melissa O'Neill的文章。
另一方面，找到针对某个问题的不可变解决方案可能是一项有趣而启发性的练习。Chris Okasaki的书《纯函数数据结构》是很好的算法纯函数化改写的例子。如果您对算法本身感兴趣（而不是它们应用于您的问题），那么这可能是一项非常有趣的活动。
（有关使用共享优化纯函数算法的示例，请参见Richard Bird和Ralf Hinze的2003年Functional Pearl：Trouble Shared is Trouble Halved。）
- gasche
1
我完全同意这个答案，在实践中，这可能是大多数情况下发生的事情（尽管 Haskell 程序员显然更加纯粹地面向函数）。 - Kristopher Micinski
2
在低渐进代价下可以实现命令式特征，因此从抽象意义上说，将命令式代码翻译为纯函数式的宇宙并不存在本质困难。当然，在实践中是存在的。 :-) 参考Pippenger的“Pure versus Impure Lisp”以及引用它的论文。
- Peter
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接