openlang
语言设计与语法

foldl composes fine and leaks anyway

后续讨论 6 ↓查看参考资料 ↓

foldl (+) 0 over a long list is the smallest space leak I know, and it's a composition problem more than an arithmetic one. Each step builds a thunk (acc + x) that nobody forces until the end, so the accumulator grows into a chain as long as the list. foldl' from Data.List forces the accumulator to weak head normal form at every step, and the chain never forms.

The trap is that both versions have the same type. Nothing in foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b says how much memory the result holds before it is demanded. Wrap the fold in a nicer combinator and the strictness decision gets buried one level deeper, where a reader can't see it.

With optimization on, GHC's strictness analysis often rescues the plain foldl anyway. That's exactly why it catches people off guard in GHCi.

Worse, foldl' only goes to WHNF. Accumulate a pair (sum, count) and the pair constructor is evaluated while both fields stay lazy. You need strict fields or bang patterns on the components.

So I've stopped treating strictness as an optimization detail. For a combinator that folds, it belongs in the name or the docs, right next to the type.

后续讨论 6

顺着彼此的依据读下去

  1. Before anyone posts a fix, say what was measured. Total bytes allocated and peak residency are different numbers, and a leak lives in the second one. A strict fold can allocate about as much as the lazy one while keeping almost nothing live. For GHC that means reading maximum residency in the -s runtime statistics, not the allocation line above it.

  2. 接着前面的回复 ↗

    Maximum residency alone won't get you to a fix. It says there is a leak, not what it's made of. So residency first, then the heap profile by closure type, -hT, which works without a profiling build, and the thunks should stand out at once. I do this on the JVM far more than in Haskell, and the order is the same there. Only after that do you touch a single collector flag.

  3. Names and docs won't hold this. In SQL nobody even calls it laziness, and the planner decides what actually runs from a composed view. PostgreSQL inlines a non-recursive, side-effect-free CTE that is referenced once, unless you write MATERIALIZED, so wrapping a subquery in WITH stopped acting as an optimization fence in version 12. Same query text, different evaluation, and no doc comment noticed. ilse's GHCi point says the same about GHC.

  4. We could give the accumulator its own type with strict fields, something like data Acc = Acc !Int !Int. Then foldl' forcing the outer constructor forces both counts too, and the strictness is written once, where the data is defined, instead of at every fold. That may be enough for most of these combinators.

  5. 接着前面的回复 ↗

    That holds for Acc !Int !Int because WHNF of an Int is the whole number. It stops holding once a field is a container. With data Acc = Acc !Int !(Map String Int) the bang evaluates the map, and since Map is strict in its keys and structure that builds the whole tree, but the values stay as they were. So Map.insertWith (+) k 1 m from Data.Map.Lazy still stacks (+) thunks in the values. The strict field is fine. The fix for the values is importing Data.Map.Strict, whose functions evaluate a value to WHNF before storing it.

    So the strictness ends up written in two places, the field and the import, and only the first sits next to the type.

  6. 接着前面的回复 ↗

    A third place, StrictData. The pragma makes every constructor field in the module strict unless it is marked ~. It sits at the top of the file, further from the type than a bang, and it still stops at WHNF, so the Map values are untouched.

同一个问题的其他角度

  1. 语言设计与语法

    Empty reductions return the identity

    Reduce over an empty vector. APL answers. Each primitive carries its identity. Zero for plus. One for times and for and. ⌈/⍬…

    回复 3apl
  2. 语言设计与语法

    Returning from a Common Lisp handler means declining

    Neat abbreviation. I'd still like to see what it's agreeing to. The wrapper macro installs a handler around a parser, and the…

    回复 4common-lisp
  3. 语言设计与语法

    age>=18=>allow and the Racket reader

    Rule authors want to write age>=18=>allow, no spaces, no parentheses. Racket's default reader may hand that over as one symbo…

    回复 8racket