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

Question

假设我有一个很大的列表，我想在上面执行多个 map、filter 和 fold/reduce 调用。为了清晰和表现力，这应该通过传递给 map/filter/fold 的小 lambda 函数来完成。但是，据我所知，这些实际上每次都遍历列表，在其上调用 lambda(尽管可能是内联的)并生成一个新列表。如果是这种情况，我可以编写一个 for-each 循环并将所有 lambda 表达式合并到它的主体中。

我测量了一个简单的 map/filter/reduce 算法的执行时间和 Python 中相应的命令式 for-each 循环，后者比我预期的快两倍多，但我知道 Python 在这方面并不是最好的语言.

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

Answer 1

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

使用的一个术语或方法是 "fusion" (也称为流或 map fusion)，其目标是智能地内联迭代转换，其模式类似于 map f . map g = map (f . g) .这主要是在编译器的帮助下完成的，但可以在这些函数的“正常”实现上工作(如果它们有点聪明的话)。

另一种方法是通过累加所有中间闭包手动执行这种内联，并且仅在实际需要值时才应用组合转换(这与惰性求值密切相关，这在某些语言中，例如 Haskell 中会完成)自动地)。这些东西可以在 Scala 的 views 中找到。和 Stream s 或 Clojure 的 transducers (不过，它以更复杂的方式工作)。这些懒惰的东西的问题在于它们更容易遇到空间问题(我听说过)。

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