是否有'span`和`fol​​dl'的优化组合,或者GHC会优化组合吗？

Question

假设我想要列出列表中的所有元素,但不包括第一个负数,并返回数字和列表的其余部分.这样做的简单方法是

addPos l = s `seq` (s,back)
  where
    (front, back) = span (>= 0) l
    s = sum front

其中,seq应确保没有人意外通过强制和前背部建立一个巨大的thunk.

然而,我很好奇GHC是否足够智能以避免创建中间前沿列表.此外,有人可以解释(如果有的话)它会发现它可以严格累积总和吗？Prelude定义使用foldl而不是foldl',GHC定义看起来相同.

Answer 1

当我们谈论编译器优化中间列表时,通常我们谈论的是在GHC的RULESpragma中实现的"融合" ; 你可以了解它是如何工作的,以及哪些列表功能在这里是"好消费者"和"生产者" .

不幸的是,它看起来不像span是一个"好的制作人".你可以通过询问GHC的核心输出并获得一系列触发的规则来亲眼看到ghc -O2 -ddump-simpl -dsuppress-module-prefixes -dsuppress-uniques -ddump-core-stats -ddump-inlinings -ddump-rule-firings test.hs

这是一个清理输出:

Rule fired: Class op >=
Rule fired: SPEC Data.List.sum
Inlining done: geInt{v r3n} [gid]
Inlining done: sum_sum1{v rkV} [gid]
Inlining done: span{v r1Q} [gid]
Inlining done: sum_sum'1{v rl6} [gid]

==================== Tidy Core ====================
Result size of Tidy Core = {terms: 24, types: 27, coercions: 0}

addPos1 :: Int -> Bool
addPos1 = \ (ds :: Int) -> case ds of _ { I# x -> >=# x 0 }

addPos [InlPrag=INLINE[0]] :: [Int] -> (Int, [Int])
addPos =
  \ (w :: [Int]) ->
    case $wspan @ Int addPos1 w of _ { (# ww1, ww2 #) ->
    case $wsum' ww1 0 of ww3 { __DEFAULT -> (I# ww3, ww2) }
    }

你可以看到我们称之为某种重写/专门化span,然后是a sum.

您可能会看到vector库是否可以融合它们,或者看看性能如何比较有趣.