Haskell 中的融合是什么？
What is fusion in Haskell?
我时常在 Haskell 文档中注意到以下内容：
（例如 Data.Text）：
Subject to fusion
什么是 fusion 以及如何使用它？
一般来说，融合是指以摆脱中间数据结构为目的的转换。您 fuse 函数调用导致浪费的内存分配到更有效的东西中。这实际上是 IMO Haskell 纯粹的最大应用之一。而且您几乎不需要做任何事情来获得它，它通过 GHC 编译器免费提供。
Haskell纯
因为Haskell是纯的，所以我们得到这个叫做referential transparency的东西，它（来自link），意味着"expression always evaluates to the same result in any context"1。这意味着我可以在不改变程序实际输出的情况下进行非常一般的程序级操作。例如，即使不知道 x、y、z 和 w 是什么，我也总是知道
((x ++ y) ++ z) ++ w
的计算结果与
相同
x ++ (y ++ (z ++ w))
然而第二个实际上将涉及较少的内存分配（因为 x ++ y 需要重新分配输出列表的整个前缀）。
重写规则
事实上，我们可以做很多这样的优化，而且，因为 Haskell 是纯粹的，我们基本上可以移动整个表达式（替换 x，y、z 或 w 对于实际列表或计算结果为上述示例中的列表的表达式没有任何改变）。这变成了一个相当机械的过程。
此外，事实证明您可以为高阶函数 (Theorems for free!) 提出很多等价项。例如，
map f (map g xs) = map (f . g) xs
无论f、g、xs是什么（两者在语义上是相等的）。然而，虽然这个等式的两侧产生相同的价值输出，但左侧的效率总是更差：它最终为中间列表 map g xs 分配 space，然后立即被丢弃。我们想告诉编译器，每当它遇到类似 map f (map g xs) 的东西时，用 map (f . g) xs 替换它。而且，对于 GHC，这是通过 rewrite rules:
{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}
f、g 和 xs 可以与任何表达式匹配，而不仅仅是变量（因此 map (+1) (map (*2) ([1,2] ++ [3,4])) 被转换为 map ((+1) . (*2)) ([1,2] ++ [3,4]).（, so I compiled a list). This paper 解释了 GHC 重写规则的动机和工作原理。
这就是 GHC 优化的方式 map?
实际上，不完全是。上面的东西是short-cut fusion。这个名字有点暗示缺点：它不能很好地扩展并且调试起来很烦人。您最终不得不为相同公共功能的所有安排编写大量临时规则。然后，你希望重复应用重写规则能很好地简化你的表达式。
事实证明，在某些情况下，我们可以通过组织重写规则来做得更好，这样我们就可以建立一些中间范式，然后制定针对该中间形式的规则。这样，我们开始获得 "hot" 个重写规则路径。
这些系统中最先进的可能是 stream fusion targeting coinductive sequences (basically lazy sequences like lists). Check out this thesis and this paper (which is actually pretty much how the vector 软件包已实施）。例如，在 vector 中，您的代码首先转换为涉及 Streams 和 Bundles 的中间形式，以该形式进行优化，然后转换回向量。
还有……Data.Text?
Data.Text 使用流融合来最小化发生的内存分配次数（我认为这对于严格变体尤其重要）。如果你检查大部分 source, you'll see that the functions "subject to fusion" actually manipulate Streams（它们是一般形式 unstream . (stuff manipulating stream) . stream）并且有一堆 RULES pragmas 用于转换 Streams。最后，这些函数的任意组合都应该被融合，这样只需要进行一次分配。
那么，我的日常编码需要带走什么？
了解您的代码何时进行融合的唯一真正方法是深入了解所涉及的重写规则并深入了解 GHC 的工作原理。也就是说，您 应该 做一件事：尽可能尝试使用非递归高阶函数，因为它们可以（至少现在是这样，但通常总是这样）更多）容易融合。
并发症
因为 Haskell 中的融合是通过重复应用重写规则而发生的，只要知道整个 "fused" 程序与您的原始程序做同样的事情就足以让您自己相信每个重写规则的正确性做。除了与程序终止有关的边缘情况。例如，有人可能认为
reverse (reverse xs) = xs
但这显然不是真的，因为 head $ reverse (reverse [1..]) 不会终止，但 head [1..] 会。 More information from the Haskell Wiki.
1 这实际上是正确的，前提是在这些上下文中表达式保持相同的类型。
我时常在 Haskell 文档中注意到以下内容：
（例如 Data.Text）：
Subject to fusion
什么是 fusion 以及如何使用它？
一般来说，融合是指以摆脱中间数据结构为目的的转换。您 fuse 函数调用导致浪费的内存分配到更有效的东西中。这实际上是 IMO Haskell 纯粹的最大应用之一。而且您几乎不需要做任何事情来获得它，它通过 GHC 编译器免费提供。
Haskell纯
因为Haskell是纯的，所以我们得到这个叫做referential transparency的东西，它（来自link），意味着"expression always evaluates to the same result in any context"1。这意味着我可以在不改变程序实际输出的情况下进行非常一般的程序级操作。例如，即使不知道 x、y、z 和 w 是什么，我也总是知道
((x ++ y) ++ z) ++ w
的计算结果与
相同 x ++ (y ++ (z ++ w))
然而第二个实际上将涉及较少的内存分配（因为 x ++ y 需要重新分配输出列表的整个前缀）。
重写规则
事实上，我们可以做很多这样的优化，而且，因为 Haskell 是纯粹的，我们基本上可以移动整个表达式（替换 x，y、z 或 w 对于实际列表或计算结果为上述示例中的列表的表达式没有任何改变）。这变成了一个相当机械的过程。
此外，事实证明您可以为高阶函数 (Theorems for free!) 提出很多等价项。例如，
map f (map g xs) = map (f . g) xs
无论f、g、xs是什么（两者在语义上是相等的）。然而，虽然这个等式的两侧产生相同的价值输出，但左侧的效率总是更差：它最终为中间列表 map g xs 分配 space，然后立即被丢弃。我们想告诉编译器，每当它遇到类似 map f (map g xs) 的东西时，用 map (f . g) xs 替换它。而且，对于 GHC，这是通过 rewrite rules:
{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}
f、g 和 xs 可以与任何表达式匹配，而不仅仅是变量（因此 map (+1) (map (*2) ([1,2] ++ [3,4])) 被转换为 map ((+1) . (*2)) ([1,2] ++ [3,4]).（
这就是 GHC 优化的方式 map?
实际上，不完全是。上面的东西是short-cut fusion。这个名字有点暗示缺点：它不能很好地扩展并且调试起来很烦人。您最终不得不为相同公共功能的所有安排编写大量临时规则。然后，你希望重复应用重写规则能很好地简化你的表达式。
事实证明，在某些情况下，我们可以通过组织重写规则来做得更好，这样我们就可以建立一些中间范式，然后制定针对该中间形式的规则。这样，我们开始获得 "hot" 个重写规则路径。
这些系统中最先进的可能是 stream fusion targeting coinductive sequences (basically lazy sequences like lists). Check out this thesis and this paper (which is actually pretty much how the vector 软件包已实施）。例如，在 vector 中，您的代码首先转换为涉及 Streams 和 Bundles 的中间形式，以该形式进行优化，然后转换回向量。
还有……Data.Text?
Data.Text 使用流融合来最小化发生的内存分配次数（我认为这对于严格变体尤其重要）。如果你检查大部分 source, you'll see that the functions "subject to fusion" actually manipulate Streams（它们是一般形式 unstream . (stuff manipulating stream) . stream）并且有一堆 RULES pragmas 用于转换 Streams。最后，这些函数的任意组合都应该被融合，这样只需要进行一次分配。
那么，我的日常编码需要带走什么？
了解您的代码何时进行融合的唯一真正方法是深入了解所涉及的重写规则并深入了解 GHC 的工作原理。也就是说，您 应该 做一件事：尽可能尝试使用非递归高阶函数，因为它们可以（至少现在是这样，但通常总是这样）更多）容易融合。
并发症
因为 Haskell 中的融合是通过重复应用重写规则而发生的，只要知道整个 "fused" 程序与您的原始程序做同样的事情就足以让您自己相信每个重写规则的正确性做。除了与程序终止有关的边缘情况。例如，有人可能认为
reverse (reverse xs) = xs
但这显然不是真的，因为 head $ reverse (reverse [1..]) 不会终止，但 head [1..] 会。 More information from the Haskell Wiki.
1 这实际上是正确的，前提是在这些上下文中表达式保持相同的类型。