haskell - Haskell 中的融合是什么？

Question

我时不时地注意到 Haskell 文档中的以下内容:
(例如在 Data.Text 中):

Subject to fusion

什么是融合以及如何使用它？

Answer 1

一般来说，融合是指旨在摆脱中间数据结构的转换。您将导致浪费内存分配的函数调用融合为更有效的方法。这实际上是 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 的中间形式。 s 和 Bundle s，以这种形式优化，然后被转换回向量。

还有... 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 这实际上是正确的，前提是在这些上下文中表达式保持相同的类型。