4

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

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

where the seq should ensure that no one accidentally builds a huge thunk by forcing the back before the sum.

I'm curious, however, whether GHC is smart enough to avoid creating the intermediate front list. Also, could someone explain how (if at all) it figures out that it can accumulate strictly in sum? The Prelude definition uses foldl rather than foldl', and the GHC definition looks equivalent.

2
  • 2
    "Also, could someone explain how (if at all) it figures out that it can accumulate strictly in sum?" foldl is inlined and plus is strict. The strictness analyser does everything else. foldl' is rarely needed for this reason.
    – Philip JF
    Jan 22, 2014 at 6:01
  • span is more or less 'takeWhile' p xs, 'dropWhile' p xs. But why do you need to use span if you got a performance problem with your addPlus ? Study the haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html as jberryman says.
    – Jonke
    Jan 22, 2014 at 8:41

1 Answer 1

5

When we talk about the compiler optimizing away intermediate lists usually we're talking about "fusion" implemented in GHC's RULES pragma; you can reas about how that works, and which list functions are "good consumers" and "producers" here.

Unfortunately it doesn't look like span is a "good producer". You can see for yourself by asking to look at GHC's core output and get a list of the rules that fired with ghc -O2 -ddump-simpl -dsuppress-module-prefixes -dsuppress-uniques -ddump-core-stats -ddump-inlinings -ddump-rule-firings test.hs

Here is a cleaned up 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) }
    }

You can see we call some sort of rewritten/specialized span, followed by a sum.

You might see if the vector library can fuse them, or see how the performance compares for fun.

1
  • Thanks for the research! The next question, of course, is whether there's a standard function for combining foldl with span, or whether I just need to roll my own.
    – dfeuer
    Jan 22, 2014 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.