我时不时地在Haskell文档中注意到以下内容:
(例如 Data.Text 中):
什么是融合，该如何使用？
最佳答案
通常，融合是指旨在摆脱中间数据结构的转换。您将函数调用融合在一起，这将导致浪费的内存分配，从而使效率更高。实际上，这实际上是IMO Haskell的最大应用之一。而且您几乎不需要执行任何操作即可获得它，它是通过GHC编译器免费提供的。
Haskell是纯洁的
因为Haskell是纯净的，所以我们将其称为referential transparency，它(从链接中)表示“在任何情况下表达式始终求值相同的结果” 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分配了空间，该列表立即被丢弃。我们想告诉编译器，每当遇到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])(There doesn't appear to be a good way to search for rewrite rules，所以我编译了list)。This paper解释了GHC重写规则的动机和原理。这就是GHC如何优化
map的方式吗？其实不是。上面的是short-cut fusion。这种名称的隐含缺点是:它伸缩性不佳，并且很烦人调试。您最终必须为大量相同功能的所有安排编写大量的临时规则。然后，您希望重复应用重写规则可以很好地简化您的表达式。
事实证明，在某些情况下，我们可以通过组织重写规则来做得更好，这样我们可以建立一些中间范式，然后针对这些中间范式制定规则。这样，我们开始获得重写规则的“热门”路径。
这些系统中最先进的可能是针对共导序列的stream fusion(基本上是像列表这样的惰性序列)。检查this thesis和this paper(实际上是
vector 包的实现方式)。例如，在vector中，您的代码首先被转换为涉及Stream和Bundle的中间形式，并以该形式进行了优化，然后被转换回 vector 。还有...
Data.Text？Data.Text使用流融合来减少发生的内存分配数量(我认为这对于严格的变体特别重要)。如果您检查source，您会看到“受融合”的函数实际上实际上在大多数情况下操纵 Stream s(它们的格式一般为unstream . (stuff manipulating stream) . stream)，并且有一堆RULES编译指示符用于转换Stream s。最后，应该融合这些功能的任何组合，以便只需要进行一次分配。那么，我日常编码需要带些什么呢？
知道何时对代码进行融合的唯一真实方法是对所涉及的重写规则有充分的了解，并很好地理解GHC的工作原理。就是说，您应该做一件事:尝试尽可能使用非递归的高阶函数，因为这些函数(至少目前是这样，但总的来说总是会越来越容易)容易融合。
并发症
由于Haskell中的融合是通过重复应用重写规则而发生的，因此足以使自己相信每个重写规则的正确性，从而知道整个“融合”程序与原始程序具有相同的作用。除非存在与程序终止有关的极端情况。例如，有人可能会认为
reverse (reverse xs) = xs
但这显然是不正确的，因为
head $ reverse (reverse [1..])不会终止，而head [1..]会终止。 More information from the Haskell Wiki。1实际上，只有在这些情况下表达式保持相同的类型时，这才是正确的。