Using BangPatterns to Eliminate Space Leaks in Haskell Accumulators

Problem: Space leak in a naïve sum

When you write a simple recursive sum over a list, the accumulator is lazy by default. Each recursive step builds a thunk for the next accumulator value instead of evaluating it immediately. In a tight loop this creates a chain of unevaluated expressions that grows with the input size, turning what should be O(1) space into O(n).

Example of the leak

sumLazy :: [Int] -> Int
sumLazy xs = go 0 xs
  where
    go acc []     = acc
    go acc (y:ys) = go (acc + y) ys

Calling sumLazy [1..1000000] builds a million thunks before any addition is performed, which you can see as a rising heap profile.

Solution: BangPatterns on the accumulator

The BangPatterns extension lets you mark a pattern as strict, forcing its evaluation to weak head normal form (WHNF) before the function body runs. By placing an exclamation mark (!) before the accumulator argument in both the pattern and the recursive call, you ensure each step evaluates the accumulator immediately.

Strict version

sumStrict :: [Int] -> Int
sumStrict xs = go 0 xs
  where
    go !acc []     = acc
    go !acc (y:ys) = go (acc + y) ys

The !acc in the pattern forces acc to be evaluated before the body of go executes. The same annotation on the recursive call forces the new accumulator value before the next iteration.

Verification

To confirm the improvement:

1. Enable the extension: add {-# LANGUAGE BangPatterns #-} at the top of the file or compile with -XBangPatterns.
2. Compile with optimisation: ghc -O2 Sum.hs.
3. Run the program with runtime statistics: ./Sum +RTS -s.
4. Compare the total alloc and max residency fields between the lazy and strict versions. The strict version should show a constant residency (e.g., a few kilobytes) regardless of list length, while the lazy version’s residency grows linearly.

In GHCi you can also use :set +s after loading the module and observe that the strict version returns instantly, whereas the lazy version pauses as it builds thunks.

Trade‑off and limitation

BangPatterns increase verbosity and shift evaluation earlier. If you accidentally make a component strict that should remain lazy (for example, the list spine in a producer/consumer pipeline), you may lose the ability to work with infinite lists or to short‑circuit on early termination. Moreover, BangPatterns only enforce WHNF; deep structures can still accumulate laziness in their fields, so you may need seq or deepseq for full strictness.

Actionable closing

When you notice a space leak in an accumulator‑style function, try adding a BangPattern to the accumulator first. Verify the change with +RTS -s or a heap profile. If the leak persists, examine whether the leak is in the accumulator’s elements rather than the accumulator itself, and consider deeper strictness tools. This small annotation often turns an O(n) space algorithm into O(1) with minimal code change.