是否有`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的RULES pragma中實現的「融合」你可以關注它是如何工作的，以及哪些列表功能是「好消費者」和「生產者」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庫是否可以將它們融合，或者看看性能如何比較以獲得樂趣。