Haskell平台:嵌套函数和优化

Question

在haskell平台的许多功能的实现中有一个非常常见的模式困扰我,但我无法找到解释.它是关于使用嵌套函数进行优化的.

嵌套函数在where子句用于进行尾递归的原因对我来说非常清楚(如长度),但内部函数与顶级函数具有完全相同类型的目的是什么？例如,它发生在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

我怀疑它可能与memoization有关,但我不确定.

---

编辑:由于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

我了解这个宏的作品,但我还是不明白为什么go一起STRICT_1_OF_2(go)不应该在顶层到位的移动member.

也许这不是因为优化,而是因为风格选择？

---

编辑2:我增加了INLINABLE和INLINE部分从所述一组模块.乍一看,我没想到他们可以和它有关.

Answer 1

在本地工作者周围拥有INLINABLE(或INLINE)包装器的一个直接好处是专业化.member在调用站点上使用固定元素类型定义的方式,Ord可以丢弃字典并将相应的compare函数内联或至少作为静态参数传递.

使用直接递归定义,member成为一个循环破坏者并且没有内联,因此呼叫站点专业化没有完成 - 至少是在INLINABLEpragma 之前的故事.

使用INLINABLEpragma,调用站点专业化确实发生,字典被删除,​​但我有几次尝试没有设法编写一个member与当前有效的直接递归.但是,有了INLINE法律依据,法律仍然存在,一个循环破坏者没有内联; 因为member这意味着没有可以消除字典的呼叫站点专业化.

因此,可能不再需要以该样式编写函数,但实际上是调用站点专业化.

Answer 2

GHC无法内联递归函数.方式member是定义的,递归是局限的go,member本身不是递归的,可以内联.

来自GHC用户指南:

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