连续映射/过滤/折叠调用的优化

Question

假设我有一个大列表，我想在其中执行多个映射、筛选和折叠/减少调用。为了清晰和表现性，这应该通过传递给map/filter/折叠的小lambda函数来完成。然而，据我所知，它们实际上每次都遍历列表，调用上面的lambda (可能是内联的)并生成一个新的列表。如果是这样的话，我可以只编写一个for-每一个循环，并将所有lambda合并到它的体内。

我测量了一个简单的map/filter/ know算法的执行时间和对应的命令式-- Python中的每个循环和后者的执行速度比我预期的快两倍多，但我知道Python不是这方面最好的语言。

我的问题是:编译器是否有可能找出它们，并以某种方式将它们合并成一个循环？有任何编译器可以这样做吗？我主要对函数式语言(Haskell、Erlang/Elixir、Scala)感兴趣，但也很高兴听到其他语言(Rust的实现，LINQ)。

Answer 1

是的，这种优化已经被考虑过很多次了。

使用的一个术语或方法是“融合” (也称为流或map融合)，它的目标是以map f . map g = map (f . g)这样的模式智能地内联迭代转换。这主要是在编译器的帮助下完成的，但是可以对这些函数的“正常”实现进行工作(如果它们是智能的)。

另一种方法是通过累积所有中间闭包来手动执行这种内联，并且只在实际需要值时应用组合转换(这与惰性计算密切相关，在某些语言中，如Haskell，这是自动完成的)。这种情况可以在Scala的视图和Stream中找到，或者可以在Clojure的换能器中找到(尽管它们的工作方式比较复杂)。这些懒惰的东西的问题在于它们更容易遇到太空问题(我听说过)。

Python中的迭代器(以及C#的IEnumerable/LINQ组件，以及Java的新Stream)原则是通过后一个原则工作的，涉及到语言提供的迭代支持(涉及某种内部状态)。这就是为什么xs = map(print, range(10))不会立即打印任何内容，只能遍历一次；在迭代的每一步，嵌套迭代器都会相互询问下一个值，转换它，并更新它们的状态。(而且您测量到的差异可能更多地是由于这个涉及的机器而不是重复的迭代。)