关于Foldable类中foldl'与foldr'默认定义的疑问

Great question! This is a common point of confusion with Haskell's Foldable strict folds—let's unpack why the standard library uses that seemingly convoluted definition instead of the more intuitive one you proposed.

First, let's restate both definitions clearly for reference:

Standard Library Definition #

class Foldable t where
  -- ...
  foldr' f z0 xs = foldl f' id xs z0
    where f' k x z = k $! f x z
  -- ...
  foldl' f z0 xs = foldr f' id xs z0
    where f' x k z = k $! f z x
  -- ...

Proposed Intuitive Definition #

class Foldable t where
  -- ...
  foldr' f = foldr (\x z -> f x $! z)
  -- ...
  foldl' f = foldl (\z x -> flip f x $! z)
  -- ...

1. Avoiding Stack Overflows #

The biggest practical reason is stack safety. Let's take foldr' as an example:

• Your intuitive version builds on foldr, which for lists (and many other Foldable instances) uses a right-associative, non-tail-recursive structure. Even with $! to force strictness in each step, processing a very long list will create a deep nested thunk chain. When this chain is finally evaluated, it will consume the call stack and cause a stack overflow.
• The standard library's foldr' uses foldl (a left-associative, tail-recursive fold) to build a chain of continuation functions. foldl is optimized by GHC into a loop (via tail-call elimination), so even for huge structures, it won't overflow the stack. The $! ensures each step of the fold is strictly evaluated, avoiding lazy thunk buildup.

The same logic applies to foldl': using foldr to build continuations ensures stack safety, whereas building on foldl directly can lead to thunk accumulation and stack overflows for large inputs.

2. Consistent Strictness Across All Foldable Instances #

Foldable is a generic type class—its instances range from simple lists to custom data structures like trees, streams, or Maybe. Not all instances implement foldr/foldl with the same level of strictness:

• Your intuitive version relies entirely on the underlying foldr/foldl implementation of the instance. If an instance's foldr is lazy (e.g., a lazy tree that stops traversing early for certain operations), your foldr' might not fully traverse the structure or evaluate all steps strictly.
• The standard definition bypasses this by using the opposite fold (e.g., foldl for foldr') to enforce strict traversal of the entire structure, regardless of how the instance's native foldr behaves. This guarantees consistent strictness for every Foldable type.

3. Maximizing Code Reuse #

The Foldable type class only requires implementing either foldr or foldl—the other fold gets a default implementation via the first. The standard strict folds reuse this same pattern:

• If you only implement foldr for your custom Foldable instance, foldl' will automatically work correctly using the default foldr-based definition.
• Your intuitive version would require both foldr and foldl to be implemented (or rely on the default lazy folds) which could lead to inconsistent behavior or broken strictness for instances that only implement one fold.

In short, the standard definitions trade a bit of initial readability for stack safety, consistent strictness across all instances, and better compatibility with the Foldable type class design.

内容的提问来源于stack exchange，提问作者Dannyu NDos