Laziness, Thunks and Strictness

Evaluated only when needed

Haskell uses lazy evaluation (call-by-need): an expression is not evaluated until its value is required, and then only once, with the result shared. Unevaluated expressions are stored as thunks. Benefits: infinite structures ([1 ..], cycle, self-referential definitions like the Fibonacci stream), separating generation from consumption (take 10 (filter isPrime [2 ..])), and avoiding work whose result is never used. Costs: space leaks, where many thunks pile up, for example with foldl or lazy accumulators in records, and less predictable memory use. Tools for strictness: seq a b evaluates a to weak head normal form (the outermost constructor) before returning b; $! is strict application; the BangPatterns extension (go !acc (x:xs)) forces arguments; strict fields in data types (data P = P !Int !Int) and the StrictData extension; strict containers such as Data.Map.Strict; and deepseq/force for full evaluation. The usual guideline: lazy data structures for streams and control, strict accumulators and record fields for numbers and state.

Infinite lists and strict accumulators

Laziness for streams, bang patterns for accumulation.

{-# LANGUAGE BangPatterns #-}
import Data.List (foldl')

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)       -- defined in terms of itself

primes :: [Int]
primes = sieve [2 ..]
  where
    sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
    sieve []       = []

-- strict accumulators: no thunk build-up even for millions of elements
mean :: [Double] -> Double
mean = go 0 (0 :: Int)
  where
    go !s !n []       = if n == 0 then 0 else s / fromIntegral n
    go !s !n (x : xs) = go (s + x) (n + 1) xs

data Stats = Stats !Int !Int        -- strict fields: count and total
  deriving Show

addOrder :: Stats -> Int -> Stats
addOrder (Stats c t) amount = Stats (c + 1) (t + amount)

main :: IO ()
main = do
  print (take 10 fibs)                       -- [0,1,1,2,3,5,8,13,21,34]
  print (takeWhile (< 30) primes)            -- [2,3,5,7,11,13,17,19,23,29]
  print (mean [1 .. 1000000])                -- 500000.5
  print (foldl' addOrder (Stats 0 0) [120000, 30000, 80000])   -- Stats 3 230000
  let unused = error "never evaluated" :: Int
  print (fst (42 :: Int, unused))            -- 42: the second component is never needed

A to-do note instead of the work

A thunk is a sticky note saying "compute this later". Laziness is great when many notes are never needed, but if you keep stacking notes ("add 1 to the result of the note below") instead of doing the sums, the pile can fill the whole office.

Quick check: What is a common cause of space leaks in Haskell?

• Using strict folds
• Using pattern matching
• Writing type signatures
• Accumulating unevaluated thunks, for example with lazy foldl or lazy record fields