确实存在一些算法和数据结构，即使使用惰性方式，也没有已知的渐进有效的纯函数式解决方案（即可以在纯lambda演算中实现的一种解决方案）。

• 上述的并查集
• 哈希表
• 数组
• 一些图算法
• ......

然而，我们假设在“命令式”语言中，对内存的访问是O（1），而理论上不能在渐进意义下（即对于无限制问题大小）如此，访问一个大数据集中的内存总是O（log n），这可以在函数式语言中模拟。

此外，我们必须记住，实际上所有现代的函数式语言都提供可变数据，甚至Haskell在不牺牲纯度的情况下提供了它（使用ST monad）。

根据Pippenger [1996]的说法，当比较一个Lisp系统是纯函数式（并且具有严格的求值语义，不是lazy）和一个可以改变数据的系统时，针对一个在非纯的Lisp系统中运行时间为O（n）的算法，可以将其转换为一个在纯的Lisp系统中运行时间为O（nlogn）的算法（基于Ben-Amram和Galil [1992]关于仅使用指针模拟随机存储器的工作）。Pippenger还证明了存在这种算法是最佳的，因为在非纯系统中的O（n）问题在纯系统中是Ω（nlogn）。

有一些关于本文需要说明的地方。最重要的是它没有涉及到惰性函数式语言，例如Haskell。Bird，Jones和De Moor [1997]表明Pippenger构造的问题可以在惰性函数式语言中以O（n）的时间解决，但他们没有证明（据我所知），惰性函数式语言是否能够像有变异的语言一样以相同的渐近运行时间解决所有问题。

Pippenger构造的问题需要Ω（nlogn）来实现该结果，因此不一定代表实际的世界问题。问题上有一些意想不到的限制，但对于证明的正确性是必要的；特别是，该问题要求在线计算结果，而不能访问未来的输入，输入由来自无限可能原子集合的原子序列组成，而不是定长集合。本文仅针对具有线性运行时间的非纯算法建立（下限）结果；对于需要更长运行时间的问题，可能可以通过需要更多的操作的过程中吸收线性问题中看到的额外的O（logn）因子。这些澄清和开放性问题被Ben-Amram [1996]简要地探讨。实践证明，许多算法在纯函数式语言中实现的效率可以和在可变数据结构语言中实现的效率相同。关于实现纯函数式数据结构的高效技巧，可以参考克丽丝·奥卡萨基（Chris Okasaki）的《纯函数式数据结构》[Okasaki 1998]（这是他的论文[Okasaki 1996]的扩展版）。

需要在纯函数式数据结构上实现算法的所有人都应该阅读奥卡萨基的书。你最多会因为用平衡二叉树模拟可变内存而得到每个操作O(log n)的运行时间损失，但在许多情况下，你可以做得更好，奥卡萨基描述了许多有用的技巧，从分摊时间技巧到实时技巧，这些技巧可以增量地执行分摊工作。纯函数式数据结构的操作和分析有些困难，但它们提供了许多好处，例如引用透明度（referential transparency），有助于编译器优化、并行和分布式计算以及版本控制、撤销和回滚等功能的实现。

还要注意，所有这些只讨论渐进的运行时间。许多实现纯函数式数据结构的技巧都会给你带来一定量的常数因子减慢，由于需要额外的簿记（bookkeeping）进行工作，并且取决于所使用语言的实现细节。纯函数式数据结构的好处可能会超过这些常数因子的减慢，因此你通常需要根据所涉及的问题做出权衡。

参考文献

• Ben-Amram，Amir和Galil，Zvi 1992年。《关于指针和地址》Journal of the ACM，39(3)，pp. 617-648，1992年7月。
• Ben-Amram，Amir 1996年。《关于Pippenger的纯Lisp和杂质Lisp的比较笔记》未发表的手稿，丹麦哥本哈根大学DIKU。
• Bird，Richard，Jones，Geraint和De Moor，Oege 1997年。《更多的急迫 ，更少的速度：惰性与热情的评估》Functional Programming 7, 5 pp. 541–547, 1997年9月。
• Okasaki，Chris 1996年。《纯函数数据结构》卡内基梅隆大学博士论文。
• Okasaki，Chris 1998年。《纯函数数据结构》剑桥大学出版社，英国剑桥。
• Pippenger，Nicholas 1996年。《纯Lisp与杂质Lisp》ACM编程语言原理研讨会，页码104–109，1996年1月。