通常,融合指的是旨在消除中间数据结构的转换。您可以将导致浪费内存分配的函数调用“融合”成更高效的东西。这实际上是 Haskell 纯粹性最大的应用之一,在 GHC 编译器的帮助下,您几乎不需要做任何事情就可以免费获得它。
Haskell 是纯函数式语言,因此我们拥有了这个被称为引用透明性的特性(来自链接),意味着“表达式在任何上下文中始终评估为相同的结果”。这意味着我可以进行非常普遍的程序级操作而不会改变程序将实际输出的内容。例如,即使不知道 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])
。(似乎没有一种好的方法来搜索重写规则,所以我编制了清单)。这篇论文解释了 GHC 重写规则的动机和工作原理。
map
的方式?实际上,并不完全是这样。以上内容是短路融合。名称有点暗示其缺点:它不能很好地扩展,而且很难调试。您最终不得不为所有相同常见函数的排列编写大量特定规则。然后,您希望反复应用重写规则将使表达式得到很好的简化。
事实证明,在某些情况下,我们可以通过组织我们的重写规则来构建一些中间正规形式,并有针对该中间形式的规则。这样,我们开始得到重写规则的“热”路径。
其中最先进的系统可能是面向共归序列(基本上是类似于列表的惰性序列)的流融合。请参见此论文和此论文(实际上几乎就是vector
包的实现方式)。例如,在vector
中,您的代码首先会被转换为涉及Stream
和Bundle
的中间形式,然后在该形式上进行优化,然后再转换回向量。
Data.Text
呢?Data.Text
使用流融合技术来最小化内存分配的次数(我认为这对于严格变量特别重要)。如果你查看源码,你会发现“需要融合”的函数大多数实际上操作Stream
s(它们的一般形式为unstream . (stuff manipulating stream) . stream
),有一堆用于转换Stream
s的规则。最终,任何这些函数的组合都应该被融合,以便只需要进行一次分配。那么,在我的日常编程中,我需要了解哪些内容呢?
唯一真正了解代码是否“需要融合”的方法是充分理解重写规则并深入了解GHC如何工作。话虽如此,还有一件事情你应该做:尽可能使用非递归高阶函数,因为这些函数可以(至少目前而言,但通常仍然更易于)轻松地进行融合。
复杂性
由于Haskell中的融合是通过重写规则的重复应用实现的,因此只需确信每个重写规则的正确性即可知道整个“融合”程序与原始程序执行相同的操作。但是,与程序终止相关的边缘情况也存在。例如,人们可能认为
reverse (reverse xs) = xs
然而,这显然不是正确的,因为head $ reverse (reverse [1..])
将不会终止,但head [1..]
会终止。有关Haskell Wiki的更多信息。
1 这实际上只有在这些上下文中表达式保持相同类型时才成立。
map g xs
),以及一个输出列表(用于 map f (map g xs)
),而右侧只分配一个输出列表。 - Alec简而言之:
融合是中间数据结构的内联函数。
这是编译器的一种优化技术。 编译器可能需要一些(有时是手写的)转换规则的支持,以便使更多的事物融合在一起,而不仅仅是显而易见的事物。
case (if a==b then Just 42 else Nothing) of
Just x -> print x
Nothing -> return ()
if a==b then print 42 else return ()
{-# RULES
"map/map" forall f g xs. map f (map g xs) = map (f . g) xs
#-}
f
和 g
可以在这里融合。我们可以说,在 map f . map g
中,map f
和 map g
也会融合,不仅仅是在创建列表和消耗列表的明显方式上,而且更深入地融合了 f
和 g
之间的关系。
stream-fusion
库的,该库多年来未编译。它早于text
和vector
库的普及使用,这些库使用流融合技术,并能编译,是现代 Haskell 的基础。被接受的答案的作者似乎完全不知道这些库的存在。从今天的角度来看,被接受的答案基本上是错误信息,而且无论如何都没有提供上述真正有价值的建议。 - Michael