Is there an optimized combination of `span` and` foldl``, or will the combination be optimized by GHC?

Question

Suppose I want to add all the elements of a list to, but not including the first negative number, and return the number and the rest of the list. A simple way to do this:

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

where he seqmust ensure that no one accidentally builds a huge piece, forcing him back to the sum.

I'm curious, however, how smart the GHC is so as not to create an intermediate front list. In addition, can someone explain how (if at all) he finds out that he can accumulate strictly in total? The Prelude definition uses foldl, not foldl ', and the GHC definition looks equivalent.

Answer 1

When we talk about a compiler that optimizes intermediate lists, we usually talk about "fusion" implemented in the GHC RULESpragma; You can talk about how this works, and which list features are “good consumers” and “producers” here .

Unfortunately, this does not seem to be spana "good producer." You can see for yourself by asking to see the output of the GHC core and get a list of the rules that were launched usingghc -O2 -ddump-simpl -dsuppress-module-prefixes -dsuppress-uniques -ddump-core-stats -ddump-inlinings -ddump-rule-firings test.hs

Here is the cleared output:

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 , , .