performance - 编译器优化的函数式代码比命令式代码执行得更好的示例

Question

无副作用的 promise 之一，referentially transparent函数式编程是这样的代码可以被广泛优化。
报价 Wikipedia :

Immutability of data can, in many cases, lead to execution efficiency, by allowing the compiler to make assumptions that are unsafe in an imperative language, thus increasing opportunities for inline expansion.

我希望看到函数式语言编译器通过生成更好的优化代码来胜过命令式编译器的示例。

编辑:我试图给出一个具体的场景，但显然这不是一个好主意。所以我会尝试用不同的方式来解释它。

程序员将想法(算法)翻译成机器可以理解的语言。同时，翻译最重要的方面之一是人类也可以理解生成的代码。不幸的是，在许多情况下需要权衡取舍:简洁易读的代码会受到性能缓慢的影响，需要手动优化。这是容易出错、耗时的，并且会降低代码的可读性(甚至完全不可读)。

函数式语言的基础，例如不变性和引用透明性，允许编译器执行广泛的优化，这可以取代手动优化代码并使程序员从这种权衡中解脱出来。我正在寻找想法(算法)及其实现的示例，例如:

(功能)实现接近原始想法并且易于理解，

它被语言的编译器广泛优化，

如果没有降低其简洁性和可读性的手动优化，很难(或不可能)用命令式语言编写类似高效的代码。

如果有点含糊，我深表歉意，但我希望这个想法很清楚。我不想对答案进行不必要的限制。如果有人知道如何更好地表达它，我愿意接受建议。

我的兴趣不仅仅是理论上的。我想用这样的例子(除其他外)来激励学生对函数式编程产生兴趣。

起初，我对评论中建议的几个例子并不满意。再三考虑，我收回我的反对意见，这些都是很好的例子。请随时将它们扩展为完整的答案，以便人们可以评论和投票。

(一类这样的例子很可能是并行代码，它可以利用多个 CPU 内核。通常在函数式语言中，这可以很容易地完成，而不会牺牲代码的简单性(比如在 Haskell 中，通过在适当的地方添加 par or pseq )。我' 也对此类示例感兴趣，但也对其他非平行示例感兴趣。)

Answer 1

在某些情况下，相同的算法在纯上下文中会优化得更好。具体来说，stream fusion允许由一系列循环组成的算法，这些循环的形式可能多种多样:映射、过滤器、折叠、展开，组合成一个循环。

传统命令式设置中的等效优化，循环中的可变数据，必须实现完整的效果分析，这是没有人做的。

因此，至少对于作为序列上的变形和变态管道实现的算法类，您可以保证在命令式设置中不可能的优化结果。