纯function编程的效率
有没有人知道什么是纯粹的function编程，而不是命令性地（即允许副作用）编程时可能发生的最糟糕的渐近放缓？
来自itowlson的评论澄清 ：有没有什么问题最着名的非破坏性algorithm比最好的已知破坏性algorithm渐近地差，如果是这样，多less？
根据Pippenger（1996）的研究 ，当比较纯粹function性的Lisp系统（并且具有严格的评估语义，而不是懒惰的）到可以改变数据的Lisp系统时，为在O（ n ）中运行的不纯的Lisp编写的algorithm可以被翻译到一个运行在O（ n log n ）时间的纯Lispalgorithm（基于Ben-Amram和Galil [1992]关于使用指针模拟随机访问存储器的工作）。 Pippenger还build立了一些algorithm，你可以做的最好; 在纯粹的系统中，在不纯的系统中有O（ n ）是Ω（ n log n ）的问题。
关于这篇论文有几点需要注意。 最重要的是，它不涉及懒惰的函数语言，如Haskell。 Bird，Jones和De Moor [1997]certificate，Pippenger构造的问题可以在O（ n ）时间用一种懒惰的函数式语言来解决，但是他们并没有build立（而据我所知，没有人）是否不是一个懒惰的function语言，可以解决所有问题在相同的渐近运行时间作为一种语言的突变。
由Pippenger构造的问题需要Ω（ n log n ）专门构造来实现这个结果，并不一定代表实际的现实问题。 对这个问题有一些限制是有点意外的，但是certificate是必要的。 特别是这个问题要求结果是在线计算的，而不能访问未来的input，而且input由一组无限可能primefaces的primefaces序列组成，而不是一个固定大小的集合。 并且只为线性运行时间的不纯algorithmbuild立（下界）结果; 对于需要较长运行时间的问题，有可能在线性问题中看到的额外O（log n ）因子可能能够在运行时间较长的algorithm所需的额外操作的过程中被“吸收”。 Ben-Amram [1996]对这些澄清和开放性问题进行了简要的探讨。
在实践中，许多algorithm可以用纯函数式语言来实现，其效率与具有可变数据结构的语言相同。 关于高效实现纯function数据结构的技术的一个很好的参考，请参阅Chris Okasaki的“纯function数据结构”[Okasaki 1998] （这是他的论文[Okasaki 1996]的扩展版本）。
任何需要在纯数据结构上实现algorithm的人都应该阅读冈崎。 通过使用平衡二叉树模拟可变内存，每次操作总是可以减lessO（log n ）减速，但在很多情况下，您可以做得比这要好得多，而且Okasaki描述了许多有用的技术，从分期偿还技术到实时操作，一次性完成摊销工作。 纯粹function性的数据结构可能有点难以处理和分析，但是它们提供了许多好处，例如引用透明性，这对编译器优化，并行和分布式计算以及版本控制，撤消和回滚等function的实现都很有帮助。
还要注意，所有这些只讨论了渐近的运行时间。 许多实现纯粹function性数据结构的技术，由于需要额外的簿记工作以及所涉及的语言的实现细节，因此会导致一定数量的不断因素放缓。 纯function数据结构的好处可能会超过这些不变的因素减速，所以您通常需要根据问题进行权衡。
参考
- Ben-Amram，Amir and Galil，Zvi 1992. “On Pointers versus Addresses” Journal of the ACM，39（3），pp.617-648，1992年7月
- Ben-Amram，Amir 1996. “关于Pippenger纯粹和不纯Lisp比较的笔记”未发表的手稿，丹麦哥本哈根大学DIKU
- Bird，Richard，Jones，Geraint和De Moor，Oege 1997. “速度更快，速度更慢：懒惰与渴望的评价” Journal of Functional Programming 7,5 pp.541-547，1997年9月
- 冈崎克里斯1996年“纯function数据结构”博士论文，卡内基梅隆大学
- Okasaki，Chris 1998. “Purely Functional Data Structures”剑桥大学出版社，英国剑桥
- Pippenger，Nicholas 1996. “Pure Versus Impure Lisp” ACM Symposium on Programming of Programming Languages，第104-109页，1996年1月
确实有几种algorithm和数据结构，即使在懒惰的情况下，也不知道什么渐近有效的纯函数解（在纯lambda演算中可实现的）。
- 前面提到的联盟发现
- 哈希表
- 数组
- 一些图algorithm
- …
然而，我们假设在“命令式”语言中，访问内存是O（1），而在理论上，它不可能如此渐进（即无限大的问题大小），并且访问大型数据集中的内存总是O（log n） ，可以用function语言来模拟。
另外，我们必须记住，实际上所有现代的函数式语言都提供了可变数据，Haskell甚至在不牺牲纯度的情况下提供它（ST monad）。
本文声明union-findalgorithm的已知纯函数实现比它们发布的函数具有更差的渐近复杂性，它具有纯粹的函数式接口，但在内部使用可变数据。
其他答案声称永远不会有任何区别，例如，纯function性代码的唯一“缺点”是它可以并行化，让您了解function性编程社区在这些问题上的信息/客观性。
编辑：
下面的评论指出，对纯函数式编程的利弊的偏见讨论可能不是来自“函数编程社区”。 好点子。 也许我所看到的提倡者只是引用了一个“文盲”的评论。
例如，我认为这个博客文章是由可以说是function性编程社区代表的人编写的，因为这是一个“懒惰评价要点”的清单，所以提供任何缺点懒惰和纯粹的function编程可能有。 一个好的地方会取代以下（技术上是真实的，但有偏见的是不要滑稽）解雇：
如果一个严格的函数在严格的语言中具有O（f（n））的复杂性，那么它就具有一种懒惰的语言的复杂性O（f（n））。 为什么要担心？ 🙂
在内存使用上有一个固定的上限，应该没有区别。
certificate草图：给定一个固定的内存使用上界，应该能够编写一个虚拟机，执行一个命令式的指令集，其渐近复杂度与您在该机器上实际执行时相同。 这是因为您可以将可变内存作为持久数据结构进行pipe理，从而可以进行O（log（n））读取和写入操作，但是对于内存使用情况具有固定的上限，则可以拥有固定的内存量，衰变到O（1）。 因此，function实现可以是在虚拟机function实现中运行的必要版本，所以它们都应该具有相同的渐近复杂性。
我build议阅读Haskell的performance ，然后看看Alioth Language Shootout在function语言和程序/ OO中的performance。
“function性”是一组不同的特征，每一个特征都是独立有用的，而且发现它们更有用于分别查看每一个特征。
不变性
现在我熟悉它了，任何时候我都能返回一个不可变的结果，即使在一个面向对象的程序中，我总是试图这样做。 如果你有价值型的数据，那么对程序进行推理就容易多了。
作为头等types的函数
无论你想怎么称呼它，通过代表，行动或function，都是解决一整套现实世界问题的一个非常方便的方法，比如“中间孔”。
能够编写function （例如将Action转换为Action只是在某些情况下非常有用。
我们还应该在这里注意Lambda语法，因为当您将函数提升为第一类types时，您只能获得Lambda语法。 Lambda语法可以非常expression和简洁。
单子
这是一个微妙但非常强大的构造。 它和用于在C＃中创buildIEnumerable类的yield关键字一样强大。 从本质上讲，它是为你盖上一个状态机，但你的逻辑看起来是线性的。
懒惰评估和recursion
我把它们放在一起，因为虽然它们总是被作为函数式编程的特征集中在一起，但它们已经很快地变成了另外的命令式语言，很难再称它们为函数了。
S-expression式
我想我不知道该把这个放在哪里，但是将未编译的代码作为一个对象（并检查/修改它）的能力，比如Lisp S-expression式，或者LINQexpression式，在某些方面，function编程最强大的工具。 大多数新的.NET“stream利”接口和DSL使用lambda语法和LINQexpression式的组合来创build一些非常简洁的API。 更不要说Linq2Sql / Linq2Nhibernate，你的C＃代码“神奇地”作为SQL而不是C＃代码来执行。
