20

在haskell平台中实现许多功能时有一个非常常见的模式让我很困扰，但我找不到解释。这是关于使用嵌套函数进行优化。

where 子句中的嵌套函数旨在进行尾递归的原因对我来说非常清楚（如length），但是当内部函数与顶层函数具有完全相同的类型时，目的是什么？例如，它发生在Data.Set模块的许多功能中，如下所示：

-- | /O(log n)/. Is the element in the set?
member :: Ord a => a -> Set a -> Bool
member = go
  where
    STRICT_1_OF_2(go)
    go _ Tip = False
    go x (Bin _ y l r) = case compare x y of
          LT -> go x l
          GT -> go x r
          EQ -> True
#if __GLASGOW_HASKELL__ >= 700
{-# INLINABLE member #-}
#else
{-# INLINE member #-}
#endif

我怀疑这可能与记忆有关，但我不确定。

编辑：由于 dave4420 建议严格，这里是STRICT_1_OF_2可以在同一模块中找到的宏的定义：

-- Use macros to define strictness of functions.
-- STRICT_x_OF_y denotes an y-ary function strict in the x-th parameter.
-- We do not use BangPatterns, because they are not in any standard and we
-- want the compilers to be compiled by as many compilers as possible.
#define STRICT_1_OF_2(fn) fn arg _ | arg `seq` False = undefined

我理解这个宏是如何工作的，但是我仍然不明白为什么不应该在顶层移动gowith来代替.STRICT_1_OF_2(go)member

也许不是因为优化，而仅仅是因为风格选择？

编辑 2：我添加了 set 模块中的INLINABLEandINLINE部分。乍一看，我没想到他们可能与此有关。

4

2 回答 2

17

对当地工人进行INLINABLE（或）包装的一个直接好处是专业化。在调用站点使用固定元素类型定义INLINE的方式，可以丢弃字典并将适当的函数内联或至少作为静态参数传递。memberOrdcompare

使用直接递归定义，member它成为一个循环中断器并且没有内联，因此没有完成调用站点专业化 - 至少是INLINABLEpragma 之前的故事。

使用INLINABLE编译指示，调用站点专业化确实发生了，字典被消除了，但是我在几次尝试中没有设法编写一个member与当前一样有效的直接递归。但是有了INLINE编译指示，法律仍然有效，没有内联循环断路器；因为member这意味着没有可能消除字典的呼叫站点专业化。

因此，可能不再需要以这种风格编写函数，但它是为了获得调用站点的专业化。

于 2012-03-18T14:05:10.763 回答
13

GHC 不能内联递归函数。方式member被定义，递归被限制在go并且member本身不是递归的并且可以被内联。

来自GHC 用户指南：

GHC 确保内联不会永远持续下去：每个相互递归的组都被一个或多个从不内联的循环断路器切断（参见 GHC 内联的秘密，JFP 12(4) 2002 年 7 月）。GHC 尽量不选择带有 INLINE pragma 的函数作为循环断路器，但是当没有选择时，甚至可以选择 INLINE 函数，在这种情况下 INLINE pragma 将被忽略。例如，对于自递归函数，循环断路器只能是函数本身，因此始终忽略 INLINE pragma。

于 2012-03-18T11:26:09.203 回答