Laziness

Haskell evaluates expressions lazily: nothing is computed until its value is actually needed, and then it's computed at most once.

Infinite lists

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

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)

main :: IO ()
main = do
  print (take 10 primes)
  print (take 15 fibs)
  print (fibs !! 100)
  print (takeWhile (< 60) (map (* 3) [1 ..]))
  print (take 7 (cycle [1, 2, 3]))
  print (take 3 (repeat 'x'))

[2,3,5,7,11,13,17,19,23,29]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]
354224848179261915075
[3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54,57]
[1,2,3,1,2,3,1]
"xxx"

• primes and fibs are defined as infinite lists; each element is computed only when take asks for it.
• fibs refers to itself: it's a list whose later elements are sums of its earlier ones.
• cycle and repeat build infinite lists too.

(The sieve above is a classic demonstration, but it's slow for large primes — real code uses a proper algorithm or a library.)

Unused values are never computed

main :: IO ()
main = do
  let expensive = length [1 .. 100000000 :: Int]
      broken = error "this would crash"
      pair = (42, broken)
  print (fst pair)
  print (length [broken, broken, broken])
  print (if True then 1 else expensive)

42
3
1

broken is never evaluated, so it never crashes; expensive is never computed, so it costs nothing. length counts list cells without looking at the elements.

Laziness enables composition

Because of laziness, you can write programs as pipelines of simple functions without paying for intermediate results you don't use:

import Data.Char (isUpper)

main :: IO ()
main = do
  print (take 1 (filter (> 1000) (map (^ 2) [1 ..])))
  print (take 2 (filter isUpper "a sentence With Some Capitals"))

[1024]
"WS"

take 1 (filter ...) stops as soon as it finds the first match — it's as efficient as a hand-written loop with a break.

The cost: thunks and space leaks

An unevaluated expression is stored as a thunk. Building up many thunks uses memory — the classic example is foldl from the Folds lesson, or a counter that is updated a million times but never looked at. The tools to control this are:

• foldl' and other strict functions (modifyIORef', Map.insertWith on a strict map)
• seq and $!, which force a value to be evaluated now
• bang patterns (!acc), covered in Level 3

main :: IO ()
main = do
  let x = 1 + 2 :: Int
  x `seq` putStrLn "x has been evaluated"
  print $! sum [1 .. 100 :: Int]

x has been evaluated
5050

a seq b evaluates a (to its outermost constructor) before returning b; f $! x evaluates x before calling f.