Strictness of foldr' from containers

This blog post will present Haskell's evaluation order based on an interesting issue I discovered in foldr'. As a result of this investigation, the original implementation was altered. Let us start with with some basics on lazy evaluation.

Lazy evaluation

There are two important aspects of lazy evaluation: evaluation order and sharing of suspended computations (thunks). Understanding both is important for writing efficient code or to avoid space leaks. In this blog post we focus on the evaluation order. Haskell is using the so called call-by-need evaluation strategy, which is defined as: always reduce the left most, outer most redex (i.e. unevaluated reducible expression) found in an expression. Let's consider a simple example:

head (map (+1) ([1,2,3] :: [Int])

head :: [a] -> a
head (a : _) = a
head []      = error "Prelude.head: empty list"

head ((+1) 1 : map (+1) [2, 3])

Now we have three redexes that could be evaluated: either the application of head, the (+1) 1 expression or the application map. According to the call-by-need strategy we reduce the application of head first and, as a result the expression evaluates to (+1) 1, which further can be reduced to its normal form 2 :: Int (i.e. an expression without redexes).

Evaluation to weak head normal form (WHNF), means that evaluation stops as soon as at the top of the expression we get a constructor, or a lambda abstraction.

Bang patterns

The BangPatterns extension allows to influence the evaluation order. We'll explain it on a simple example: const and its strict version const':

const :: a -> b -> a
const a _ = a

const' :: a -> b -> a
const' a !_ = a

> const () (error "BANG!")
()
> const' () (error "BANG!")
CallStack (from HasCallStack):
  error, called at <interactive>:5:12 in interactive:Ghci2

A bang pattern makes a promise to evaluate the expression under the bang when the right hand side is demanded and it is not already in WHNF. These patterns are also forced when a guard protects it, e.g.

> let f !_ | False = 0; f _ = 1 in f undefined
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:21:36 in interactive:Ghci4

const' a b = b `seq` a

id :: a -> a
id a = a
  where
    Left _ = undefined

id' :: a -> a
id' a = a
  where
    !(Left _) = undefined

id' :: a -> a
id' a = b `seq` a
  where
    b@(Left _) = undefined

Strict constructor fields

For the sake of completeness, let us mention that one can use bangs within a constructor's fields (which does not require BangPattern extension). For example a strict Maybe type can be defined as

data SMaybe = SNothing | SJust !a

With this knowledge at hand we can analyse the strict fold from containers.

Strict right-associative fold

The right-associative strict fold in container-0.6.4.1 is defined in the following way:

-- | O(n). A strict version of foldr. Each application of the operator
-- is evaluated before using the result in the next application.
-- This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> Map k a -> b
foldr' f b0 = go b0
  where
    go !b Tip             = b
    go  b (Bin _ _ x l r) = go (f x (go b r)) l

Let us consider what happens when foldr' applied to a function which is lazy in its second argument. It turns out that this use of foldr' will not force the accumulator. Let us consider:

-- | @fromList [(0,0+0), (1,1+0), (2,2+0)]@
a :: Map Int Int
a = Bin 3 1 (1+0) (Bin 1 0 (0+0) Tip Tip) (Bin 1 2 (2+0) Tip Tip)

Strict right-associative fold reduction

foldr' cons nil a
---------------------------------------------- (1)
go nil (Bin 3 1 x1 l r)
  where
    x1 = 1+0
    l = Bin 1 0 (0+0) Tip Tip
    r = Bin 1 2 (2+0) Tip Tip
---------------------------------------------- (2)
go (cons x1 (go nil r)) l
---------------------------------------------- (3)
go (cons x0 (go (cons x1 (go nil r)) Tip)) Tip
  where
    x0 = 0+0
---------------------------------------------- (4)
cons x0 (go (cons x1 (go nil r)) Tip)

> let !x = foldr' (:) [] a 
> :sprint x
x = _ : _

> HeapView.buildHeapTree 100 (HeapView.asBox x)
    >>= print . HeapView.ppHeapTree
_ind (_bh (_thunk() :
            _thunk _fun (_thunk() :
              _thunk _fun
                ([] 5053632)
                (Bin (I# 2) _thunk() (Tip 4471056) (Tip 4471056) 1)
              )
            (Tip 4471056)))

Stricter right-associative fold

There is another possible definition of a strict right-associative fold:

foldr'' :: (a -> b -> b) -> b -> Map k a -> b
foldr'' f b0 = go b0
  where
    go b Tip             = b
    go b (Bin _ _ x l r) = go (f x $! go b r) l

foldr'' cons nil a
------------------------------------------------- (1)
go nil (Bin 3 1 x1 l r)
  where
    x1 = 1+0
    l = Bin 1 0 (0+0) Tip Tip
    r = Bin 1 2 (2+0) Tip Tip
------------------------------------------------- (2)
go (cons x1 $! go nil r) l
------------------------------------------------- (3)
go (cons x0 $! go (cons x1 $! go nil r) Tip) Tip
  where
    x0 = 0+0
------------------------------------------------- (4) force first $!
cons x0 $! go (cons x1 $! go nil r) Tip
------------------------------------------------- (5) force second $!
cons x0 $! cons x1 $! go nil r
------------------------------------------------- (6)
cons x0 $! cons x1 $! go (cons x2 $! go nil Tip) Tip
------------------------------------------------- (7) force last $!
cons x0 $! cons x1 $! cons x2 $! go nil Tip
------------------------------------------------- (8)
cons x0 $! cons x1 $! cons x2 $! nil

> let !x = foldr'' (:) [] a
> :sprint x
[_,_,_]

> HeapView.buildHeapTree 100 (HeapView.asBox x)
    >>= print . HeapView.ppHeapTree
_ind (_bh (_thunk() : _thunk() : _thunk() : [] 5056128))

Consequences

• foldr' gives more power to the programmer, just by making cons strict one can transform a foldr' into foldr'';
• foldr'' is in general slightly more efficient, both in terms of memory and CPU cycles, see benchmarks.