无副作用函数编程的承诺之一是可以对这些代码进行广泛优化 . 引用Wikipedia:
在许多情况下,通过允许编译器在命令式语言中做出不安全的假设,数据的不可变性可以提高执行效率,从而增加了强调内联扩展的文本机会 .
我希望看到一个示例,其中函数式语言编译器通过生成更好的优化代码来优于命令式编译器 .
Edit: 我试图给出一个特定的场景,但显然它并没有尝试以不同的方式解释它 .
程序员将想法(算法)翻译成机器可以理解的语言 . 同时,翻译最重要的一个方面是人类也可以理解产生的代码 . 不幸的是,在许多情况下需要权衡:简洁易读的代码会受到性能降低的影响,需要手动优化 . 这容易出错,耗时,并且使代码的可读性降低(完全不可读) .
功能语言的基础,例如不变性和引用透明性,允许编译器执行广泛的优化,这可以取代手动优化代码和免费程序员进行权衡 . 我正在寻找想法(算法)及其实现的示例,例如:
-
(功能)实现接近原始想法并且易于理解,
-
它被语言的编译器广泛优化,并且
-
很难(或不可能)用命令式语言编写类似的高效代码,而无需手动优化,降低其简洁性和可读性 .
如果它有点模糊,我道歉,但我希望这个想法很明确 . 我不想对答案给予不必要的限制 . 如果有人知道如何更好地表达它,我愿意接受建议 .
我的兴趣不仅仅是理论上的 . 我想使用这些例子(以及其他内容)来激发学生对函数式编程感兴趣 .
起初,我对评论中提出的一些例子并不满意 . 再想一想,我反对,这些都是很好的例子 . 请随时将它们扩展为完整的答案,以便人们可以评论和投票 .
(一类这样的例子很可能是并行化代码,可以利用多个CPU内核 . 通常在函数式语言中,这可以轻松完成而不会牺牲代码的简单性(就像在Haskell中通过在适当的位置添加par or pseq一样) . 我是对这样的例子感兴趣,但也对其他非平行的例子感兴趣 . )
4 回答
在某些情况下,相同的算法将在纯上下文中更好地优化 . 具体来说,stream fusion允许一种算法,该算法由一系列可能形式各异的循环组成: Map ,滤波器,折叠,展开,组成一个循环 .
传统命令式设置中的等效优化,循环中的可变数据,必须实现完整的效果分析,这是没有人能做到的 .
因此,至少对于作为序列上的ana-和catamorphisms的管道实现的算法类,您可以保证在命令设置中不可能的优化结果 .
Geoff大陆最近发表的一篇论文,Simon Peyton Jones,Simon Marlow,Roman Leshchinskiy(提交给ICFP 2013)描述了这样一个例子 . 摘要(粗体中有趣的部分):
这只是一个注释,而不是答案:
gcc
具有pure
属性,表明它可以考虑纯度;显而易见的原因在手册_751461中有所说明 .我认为'static single assignment'强加了一种纯度 - 见http://lambda-the-ultimate.org/node/2860或者维基百科文章 .
通过假设各种构建步骤是引用透明的,make和各种构建系统对大型项目执行得更好;因此,他们只需要重新运行已经改变输入的步骤 .
对于中小型更改,这比从头开始构建要快得多 .