haskell - 是否有 `span` 和 `foldl'` 的优化组合，或者该组合是否会被 GHC 优化？

Question

假设我想将列表的所有元素加起来，但不包括第一个负数，并返回该数字和列表的其余部分。这样做的简单方法是

addPos l = s `seq` (s,back)
在哪里
(前、后) = 跨度 (>= 0) l
s = 总和前沿

哪里seq应该确保没有人通过在总和之前强行返回而意外地构建了一个巨大的thunk。

但是，我很好奇 GHC 是否足够聪明，可以避免创建中间前列列表。另外，有人可以解释一下(如果有的话)它是如何计算出它可以严格累积的？ Prelude 定义使用 foldl 而不是 foldl'，GHC 定义看起来等效。

Answer 1

当我们谈论编译器优化掉中间列表时，通常我们谈论的是在 GHC 的 RULES 中实现的“融合”。语用；您可以了解它是如何工作的，哪些列表函数是“好的消费者”和“生产者”here .

不幸的是它看起来不像 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 ，然后是 sum .

您可能会看到 vector图书馆可以融合它们，或者看看性能如何比较有趣。