optimization - GHC真的可以永远inline map、scanl、foldr等吗？

Question

我注意到 GHC manual说“对于自递归函数，循环断路器只能是函数本身，因此总是忽略 INLINE 杂注。”

这不是说像 map 这样的常见递归函数构造的每个应用程序吗？ , zip , scan* , fold* , sum等不能内联？

当你使用它们时，你总是可以重写所有这些函数，添加适当的严格标签，或者使用像推荐的“流融合”这样的花哨技术here .

然而，这一切难道不是极大地限制了我们编写既快速又优雅的代码的能力？

Answer 1

事实上，GHC 目前不能内联递归函数。然而:

GHC 仍将专注于递归函数。例如，给定

fac :: (Eq a, Num a) => a -> a
fac 0 = 1
fac n = n * fac (n-1)

f :: Int -> Int
f x = 1 + fac x

GHC 会发现 fac用于类型 Int -> Int并生成 fac 的专用版本对于该类型，它使用快速整数运算。

这种特化在一个模块内自动发生(例如，如果 fac 和 f 在同一个模块中定义)。对于跨模块特化(例如，如果 f 和 fac 定义在不同的模块中)，用 an INLINABLE pragma 标记要特化的功能:

{-# INLINABLE fac #-}
fac :: (Eq a, Num a) => a -> a
...

有一些手动转换使函数成为非递归的。最低功耗技术是static argument transformation ，它适用于参数在递归调用中不改变的递归函数(例如许多高阶函数，例如 map 、 filter 、 fold* )。这种转变转

map f []     = []
map f (x:xs) = f x : map f xs

进入

map f xs0 = go xs0
  where
    go []     = []
    go (x:xs) = f x : go xs

这样一个电话，如

 g :: [Int] -> [Int]
 g xs = map (2*) xs

将有 map内联并成为

 g [] = []
 g (x:xs) = 2*x : g xs

此转换已应用于 Prelude 函数，例如 foldr和 foldl .

融合技术也使许多函数成为非递归的，并且比静态参数转换更强大。 Prelude 中内置的列表的主要方法是shortcut fusion。 .基本方法是编写尽可能多的函数，就像使用 foldr 的非递归函数一样。和/或 build ;那么所有的递归都被捕获到 foldr , 并且有处理 foldr 的特殊规则.

利用这种融合原则上很容易:避免手动递归，首选库函数，如 foldr , map , filter , 以及 this list 中的任何函数.特别是，以这种风格编写代码会产生“同时又快又优雅”的代码。

现代图书馆如text和 vector使用 stream fusion在幕后。 Don Stewart 写了两篇博文(1，2)在现已过时的库 uvector 中展示了这一点。 ，但相同的原则适用于文本和矢量。

与快捷方式融合一样，在文本和矢量中利用流融合原则上很容易:避免手动递归，首选已标记为“受融合”的库函数。

目前正在进行改进 GHC 以支持递归函数内联的工作。这属于 supercompilation 的总标题。 ，最近这方面的工作似乎由 Max Bolingbroke 领导。和 Neil Mitchell .