Laziness and Strictness

22.1 Lazy Evaluation

-- Values are computed only when needed (call-by-need), and at most once (sharing)
take 5 [1 ..]                         -- [1,2,3,4,5]: an infinite list is fine
let xs = map (* 2) [1 .. 1000000] in head xs   -- only one element computed
fst (1, undefined)                    -- 1: the undefined is never evaluated
length [undefined, undefined]         -- 2: elements aren't evaluated
const 1 (error "boom")                -- 1

-- Knot-tying and infinite structures
primes :: [Int]
primes = 2 : filter isPrime [3, 5 ..]
  where isPrime n = all (\p -> n `mod` p /= 0) (takeWhile (\p -> p * p <= n) primes)

-- Laziness enables modularity: generate, then consume
firstSquareOver :: Int -> Int
firstSquareOver n = head (dropWhile (<= n) (map (^ 2) [1 ..]))

22.2 Thunks, WHNF and Space Leaks

An unevaluated expression is a thunk. Weak head normal form (WHNF) means evaluated to the outermost constructor (e.g., _ : _, Just _); normal form (NF) means fully evaluated.

Rules of thumb: use strict accumulators (foldl', bang patterns), strict data fields for small numeric fields, Data.Map.Strict instead of Data.Map.Lazy when values are computed, and profile when memory grows unexpectedly.

-- Space leak: foldl builds a chain of 10 million thunks before evaluating
badSum = foldl (+) 0 [1 .. 10000000]
goodSum = foldl' (+) 0 [1 .. 10000000]       -- evaluates the accumulator at each step

-- seq forces its first argument to WHNF before returning the second
strictPair a b = a `seq` b `seq` (a, b)
-- ($!) strict application
f $! x                                         -- evaluate x to WHNF, then apply f

-- Bang patterns
{-# LANGUAGE BangPatterns #-}
mean :: [Double] -> Double
mean = go 0 0
  where
    go !s !n [] = s / fromIntegral (n :: Int)
    go !s !n (x : xs) = go (s + x) (n + 1) xs

-- Strict fields in data types
data Point = Point !Double !Double             -- fields evaluated when the constructor is evaluated
-- {-# LANGUAGE StrictData #-} makes all fields in a module strict

-- Full evaluation with deepseq
import Control.DeepSeq (deepseq, force, NFData)
let result = force (expensiveList)            -- evaluate to normal form
result `deepseq` putStrLn "done"

22.3 The ST Monad: Local Mutation, Pure Interface

import Control.Monad.ST
import Data.STRef

sumST :: [Int] -> Int
sumST xs = runST $ do                 -- runST :: (forall s. ST s a) -> a: mutation can't escape
  ref <- newSTRef 0
  mapM_ (\x -> modifySTRef' ref (+ x)) xs
  readSTRef ref

import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as MVU
sieve :: Int -> [Int]
sieve n = [i | (i, True) <- zip [0 ..] (VU.toList flags)]
  where
    flags = VU.create $ do
      v <- MVU.replicate (n + 1) True
      MVU.write v 0 False
      MVU.write v 1 False
      let loop i
            | i * i > n = pure ()
            | otherwise = do
                isP <- MVU.read v i
                if isP then mapM_ (\j -> MVU.write v j False) [i * i, i * i + i .. n] else pure ()
                loop (i + 1)
      loop 2
      pure v