连续 map/filter/fold 调用的优化
Optimization of consecutive map/filter/fold calls
假设我有一个大列表，我想在其中执行多个映射、过滤器和 fold/reduce 调用。为了清晰和表达，这应该通过传递给 map/filter/fold 的小 lambda 函数来完成。然而，据我所知，这些实际上每次都遍历列表，在其上调用 lambda（虽然可能是内联的）并生成一个新列表。如果是这种情况，我可以编写一个 for-each 循环并将所有 lambda 合并到它的主体中。
我测量了一个简单的 map/filter/reduce 算法的执行时间和 Python 中相应的命令式 for-each 循环，后者比我预期的要快两倍多，但我知道Python 在这方面不是最好的语言。
我的问题是：编译器是否有可能弄清楚这些并以某种方式将它们合并到一个循环中？有没有编译器可以做到这一点？我主要对函数式语言（Haskell、Erlang/Elixir、Scala）感兴趣，但也希望了解其他语言（Rust 的实现、LINQ）。
是的，这样的优化考虑了很多次。
使用的一个术语或方法是 "fusion" (also known as stream or map fusion)，它的目标是智能内联迭代转换，如 map f . map g = map (f . g) 这样的模式。这主要必须在编译器的帮助下完成，但可以处理这些函数的 "normal" 实现（如果它们做得有点智能）。
另一种方法是通过累积所有中间闭包来手动执行这种内联，并且仅在实际需要值时才应用组合转换（这与惰性求值密切相关，这在某些语言中会发生，像 Haskell，自动完成）。这些东西可以在 Scala 的 views and Streams, or Clojure's transducers 中找到（虽然它以更复杂的方式工作）。这些懒惰的东西的问题是它们更容易 运行 变成 space 问题（我听说过）。
Python（以及 C# 的 IEnumerable/LINQ 内容，以及 Java 的新 Streams）中的迭代器原理通过后一种原理工作，涉及一种语言-提供迭代支持（涉及一些内部状态）。这就是为什么 xs = map(print, range(10)) 不会立即打印任何东西，并且只能遍历一次；在迭代的每一步，嵌套的迭代器都会互相询问下一个值，转换它，并更新它们的状态。 （并且可能您测量到的差异更多是由于这种涉及的机器而不是重复迭代。）
假设我有一个大列表，我想在其中执行多个映射、过滤器和 fold/reduce 调用。为了清晰和表达，这应该通过传递给 map/filter/fold 的小 lambda 函数来完成。然而，据我所知，这些实际上每次都遍历列表，在其上调用 lambda（虽然可能是内联的）并生成一个新列表。如果是这种情况，我可以编写一个 for-each 循环并将所有 lambda 合并到它的主体中。
我测量了一个简单的 map/filter/reduce 算法的执行时间和 Python 中相应的命令式 for-each 循环，后者比我预期的要快两倍多，但我知道Python 在这方面不是最好的语言。
我的问题是：编译器是否有可能弄清楚这些并以某种方式将它们合并到一个循环中？有没有编译器可以做到这一点？我主要对函数式语言（Haskell、Erlang/Elixir、Scala）感兴趣，但也希望了解其他语言（Rust 的实现、LINQ）。
是的，这样的优化考虑了很多次。
使用的一个术语或方法是 "fusion" (also known as stream or map fusion)，它的目标是智能内联迭代转换，如 map f . map g = map (f . g) 这样的模式。这主要必须在编译器的帮助下完成，但可以处理这些函数的 "normal" 实现（如果它们做得有点智能）。
另一种方法是通过累积所有中间闭包来手动执行这种内联，并且仅在实际需要值时才应用组合转换（这与惰性求值密切相关，这在某些语言中会发生，像 Haskell，自动完成）。这些东西可以在 Scala 的 views and Streams, or Clojure's transducers 中找到（虽然它以更复杂的方式工作）。这些懒惰的东西的问题是它们更容易 运行 变成 space 问题（我听说过）。
Python（以及 C# 的 IEnumerable/LINQ 内容，以及 Java 的新 Streams）中的迭代器原理通过后一种原理工作，涉及一种语言-提供迭代支持（涉及一些内部状态）。这就是为什么 xs = map(print, range(10)) 不会立即打印任何东西，并且只能遍历一次；在迭代的每一步，嵌套的迭代器都会互相询问下一个值，转换它，并更新它们的状态。 （并且可能您测量到的差异更多是由于这种涉及的机器而不是重复迭代。）