一般来说,融合是指旨在消除中间数据结构的转换。你fuse函数调用会导致浪费内存分配到更有效的地方。在我看来,这实际上是 Haskell 纯粹的最大应用之一。而且你几乎不需要做任何事情就可以得到它,它通过 GHC 编译器免费提供。
哈斯克尔是纯粹的
Because Haskell is pure, we get this thing called referential transparency https://wiki.haskell.org/Referential_transparency, which (from the link), means that "expression always evaluates to the same result in any context"1. That means that I can do very general program level manipulations without changing what the program will actually output. For example, even without knowing what x
, y
, z
and w
are I always know that
((x ++ y) ++ z) ++ w
将评估为相同的事情
x ++ (y ++ (z ++ w))
然而,第二个实际上会涉及更少的内存分配(因为x ++ y
需要重新分配输出列表的整个前缀)。
重写规则
事实上,我们可以做很多这样的优化,而且,因为 Haskell 是纯粹的,我们基本上可以移动整个表达式(替换x
, y
, z
, or w
对于上面示例中计算为列表的实际列表或表达式没有任何改变)。这变成了一个相当机械的过程。
此外,事实证明,您可以想出许多高阶函数的等价形式(免费定理! https://www.mpi-sws.org/~dreyer/tor/papers/wadler.pdf)。例如,
map f (map g xs) = map (f . g) xs
无论f
, g
, and xs
是(两侧在语义上相等)。然而,虽然该等式的两侧产生相同的值输出,但左侧的效率总是较差:它最终为中间列表分配空间map g xs
,立即被丢弃。我们想告诉编译器,每当它遇到类似的情况时map f (map g xs)
,将其替换为map (f . g) xs
。而且,对于 GHC 来说,这是通过重写规则 https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#rewrite-rules:
{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}
The f
, g
, and xs
可以与任何表达式匹配,而不仅仅是变量(所以像map (+1) (map (*2) ([1,2] ++ [3,4]))
变成map ((+1) . (*2)) ([1,2] ++ [3,4])
. (似乎没有一个好的方法来搜索重写规则 https://stackoverflow.com/questions/38651602/searching-for-rewrite-rules,所以我编译了一个list https://gist.github.com/harpocrates/e95ce275a2220dfbd50b102e1e533556). 解释 GHC 重写规则的动机和工作原理。
这就是GHC的优化方式map
?
事实上,不完全是。上面的事情是捷径融合 https://wiki.haskell.org/Short_cut_fusion。这个名字有点暗示了它的缺点:它的扩展性不太好,而且调试起来很烦人。您最终必须为相同公共功能的所有安排编写大量临时规则。然后,您希望重复应用重写规则能够很好地简化您的表达式。
事实证明,在某些情况下,我们可以通过组织重写规则来做得更好,以便我们构建一些中间范式,然后制定针对该中间形式的规则。这样,我们开始获得重写规则的“热”路径。
这些系统中最先进的可能是针对共归纳序列(基本上是惰性序列,如列表)。查看这篇论文 http://community.haskell.org/~duncan/thesis.pdf and 这张纸 http://research.microsoft.com/en-us/um/people/simonpj/papers/ndp/haskell-beats-C.pdf(这实际上就是vector http://hackage.haskell.org/package/vector包已实施)。例如,在vector
,您的代码首先转换为涉及的中间形式Stream
s and Bundle
s,以这种形式进行优化,然后转换回向量。
And... Data.Text
?
Data.Text
使用流融合来最小化发生的内存分配数量(我认为这对于严格变体尤其重要)。如果您查看source https://hackage.haskell.org/package/text-1.2.2.1/docs/src/Data-Text.html#pack,你会看到“受融合”函数实际上操纵Streams https://hackage.haskell.org/package/text-1.2.2.1/docs/Data-Text-Internal-Fusion.html大部分(它们的一般形式unstream . (stuff manipulating stream) . stream
)还有一堆RULES
用于转换的实用指令Stream
s。最后,这些函数的任意组合都应该被融合,以便只需要进行一次分配。
那么,我的日常编码需要注意什么?
了解代码何时需要融合的唯一真正方法是充分了解所涉及的重写规则并充分了解 GHC 的工作原理。也就是说,有一件事你should做:尽可能尝试使用非递归高阶函数,因为它们可以(至少目前如此,但通常总是更容易)轻松融合。
并发症
因为 Haskell 中的融合是通过重复应用重写规则而发生的,所以只要知道整个“融合”程序与原始程序执行相同的操作,就足以让自己相信每个重写规则的正确性。除了与程序终止相关的边缘情况。例如,有人可能认为
reverse (reverse xs) = xs
但这显然不是真的,因为head $ reverse (reverse [1..])
还不会终止head [1..]
will. 来自 Haskell Wiki 的更多信息 https://wiki.haskell.org/Correctness_of_short_cut_fusion.
1 This is actually true only provided that in these contexts the expression maintains the same type.