纯函数式编程的效率
有谁知道在纯函数式编程而不是命令式编程（即允许副作用）时可能发生的最坏的渐近减速是什么？
itowlson 的评论澄清：是否有任何问题，最着名的非破坏性算法在渐近上比最着名的破坏性算法更差，如果是这样，差多少？
根据 Pippenger [1996]，当比较纯函数式（并且具有严格的评估语义，而不是惰性）的 Lisp 系统与可以改变数据的系统时，为运行在 O(n) 可以转换为纯 Lisp 中的算法，该算法在 O(n log n) 时间内运行（基于 Ben-Amram and Galil [1992] 关于模拟随机存取存储器的工作仅使用指针）。 Pippenger 还确定有一些算法是你能做的最好的。不纯系统中存在 O(n) 问题，纯系统中存在 Ω(n log n) 问题。
关于这篇论文有一些注意事项。最重要的是它不处理惰性函数式语言，例如 Haskell。 Bird, Jones and De Moor [1997] 证明 Pippenger 构建的问题可以在 O(n) 时间内用惰性函数式语言解决，但他们没有确定（据我所知，没有人确定）是否或者不是一种惰性函数式语言可以在与具有突变的语言相同的渐近运行时间内解决所有问题。
Pippenger 构造的问题要求 Ω(n log n) 是专门构造来实现这个结果的，并不一定代表实际的现实问题。这个问题有一些限制，有点出乎意料，但对于证明工作是必要的；特别是，该问题要求在线计算结果，而不能访问未来的输入，并且输入由来自无限可能原子集合的原子序列组成，而不是固定大小的集合。并且本文只为线性运行时间的不纯算法建立（下界）结果；对于需要更长运行时间的问题，有可能在线性问题中看到的额外 O(log n) 因素可能能够在算法所需的额外操作过程中被“吸收”运行时间更长。 Ben-Amram [1996] 简要探讨了这些说明和未解决的问题。
在实践中，许多算法可以用纯函数式语言实现，其效率与使用具有可变数据结构的语言相同。有关用于有效实现纯函数式数据结构的技术的良好参考，请参阅 Chris Okasaki's "Purely Functional Data Structures" [Okasaki 1998]（这是他的论文 [Okasaki 1996] 的扩展版本）。
任何需要在纯函数数据结构上实现算法的人都应该阅读 Okasaki。通过使用平衡二叉树模拟可变内存，您总是可以在最坏的情况下每次操作减慢 O(log n)，但在许多情况下，您可以做得比这要好得多，Okasaki 描述了许多有用的技术，从摊销技术到实际逐步完成摊销工作的时间。纯函数式数据结构可能有点难以使用和分析，但它们提供了许多好处，例如有助于编译器优化、并行和分布式计算以及版本控制、撤消和回滚等功能的实现的引用透明性。
另请注意，所有这些都只讨论渐近运行时间。许多用于实现纯函数式数据结构的技术会给您带来一定程度的常数因子减速，因为它们需要额外的簿记才能工作，以及相关语言的实现细节。纯函数式数据结构的好处可能超过这些恒定因素的减速，因此您通常需要根据所讨论的问题进行权衡。
参考
Ben-Amram, Amir 和 Galil, Zvi 1992。“关于指针与地址”ACM 杂志，39(3)，第 617-648 页，1992 年 7 月
Ben-Amram, Amir 1996。“关于 Pippenger 比较纯和不纯 Lisp 的笔记”未发表的手稿，DIKU，丹麦哥本哈根大学
Bird、Richard、Jones、Geraint 和 De Moor，Oege 1997。“更匆忙，更少速度：懒惰与急切的评估”函数式编程杂志 7，5 第 541-547 页，1997 年 9 月
Okasaki, Chris 1996 年。“纯功能数据结构”博士论文，卡内基梅隆大学
Okasaki, Chris 1998。“纯功能数据结构”剑桥大学出版社，剑桥，英国
Pippenger, Nicholas 1996。“Pure Versus Impure Lisp”ACM 编程语言原则研讨会，第 104-109 页，1996 年 1 月
确实有几种算法和数据结构没有已知的渐近有效的纯函数解决方案（在纯 lambda 演算中可以实现的一种），即使是惰性的也是如此。
上述联合发现
哈希表
数组
一些图算法
...
然而，我们假设在“命令式”语言中，对内存的访问是 O(1)，而理论上不可能如此渐近（即对于无限的问题大小），并且在一个巨大的数据集中访问内存总是 O(log n) ，可以用函数式语言来模拟。
此外，我们必须记住，实际上所有现代函数式语言都提供可变数据，Haskell 甚至在不牺牲纯度的情况下提供它（ST monad）。
This article 声称 the union-find algorithm 的已知纯函数实现都比他们发布的具有更差的渐近复杂性，后者具有纯函数接口但在内部使用可变数据。
事实上，其他答案声称永远不会有任何区别，例如，纯函数式代码的唯一“缺点”是它可以并行化，这让您了解函数式编程社区在这些问题上的知情/客观性.
编辑：
下面的评论指出，关于纯函数式编程的优缺点的有偏见的讨论可能不是来自“函数式编程社区”。好点子。也许我看到的倡导者只是，引用评论，“文盲”。
例如，我认为这个 blog post 是由可以说是函数式编程社区代表的人编写的，并且由于它是“惰性评估点”的列表，因此它是提及任何缺点的好地方懒惰和纯粹的函数式编程可能有。一个好的地方应该是代替以下（技术上正确，但偏向于不好笑）解雇：
如果严格的函数在严格语言中具有 O(f(n)) 复杂度，那么在惰性语言中它也具有 O(f(n)) 复杂度。为什么要担心？ :)
使用固定的内存使用上限，应该没有区别。
证明草图：给定内存使用的固定上限，应该能够编写一个虚拟机来执行命令式指令集，其渐近复杂度与您实际在该机器上执行一样。之所以如此，是因为您可以将可变内存作为持久数据结构进行管理，提供 O(log(n)) 读取和写入，但是在内存使用量的上限固定的情况下，您可以拥有固定数量的内存，从而导致这些衰减到 O(1)。因此功能实现可以是运行在虚拟机功能实现中的命令式版本，因此它们应该具有相同的渐近复杂度。
