Being Lazy

Lazy

Not inclined to work or exertion ¹

Overview

• Evaluation in Haskell
• Utilizing laziness
• Issues and pitfalls
• A worked example

The power of Haskell

• Purity
• Type system
• Laziness

• Rich syntax
• Sophisticated optimizer
• Extensible

• Extensive libraries

Non-strictness

In Java et al:

max(x + 5, y + 5)

(x != 0) && (y / x > 0)

boolean foo(int x, int z) {
  return (x != 0) && (z > 0);
}
...
foo(0, 3 / 0);   // Oh dear!

Non-strictness

In Haskell:

max (x + 5) (y + 5)

(x /= 0) && (y `div` x > 0)

foo :: Int -> Int -> Bool
foo x z =
  (x /= 0) && (z > 0);
}
...
foo 0 (3 `div` 0)   -- All good

Non-strictness

[42, 27, head [], 3, 17] !! 4

Lazy evaluation

doubling :: Int -> [Int]
doubling a = a : doubling (a * 2)

take 9 $ doubling 3

[3, 6, 12, 24, 48, 96, 192, 384, 768]

Infinite data structures

Given a list of names, print each one with its index in the list.

printNames :: [String] -> String
printNames names = 
  unlines $ zipWith (printf "%d: %s")
    [1..]
    names

Avoid unnecessary work

Sum the top 50 elements of a 500000 element list.

sum . take 50 . sort $ xs

Avoid unnecessary work

Timings in ghci:

sum                    xs  -- 0.16s
sum . take 50        $ xs  -- 0.00s
sum           . sort $ xs  -- 2.32s         
sum . take 50 . sort $ xs  -- 0.31s

Cyclic definitions

Generate a list of powers of 2.

Recursive function

doubling a = a : doubling (a * 2)
powersOf2  = doubling 1

Cyclic value

powersOf2 = 1 : map (* 2) powersOf2

Cyclic definitions

Create two values that refer to each other.

data Cat   = Cat   
  {cname :: String, victim    :: Mouse}

data Mouse = Mouse
  {mname :: String, tormentor :: Cat}

tom   = Cat   "Tom"   jerry
jerry = Mouse "Jerry" tom

Lazy IO

Read lines from a large file, reverse the characters of each line and write the result to a new file.

main = do
  i <- readFile "input"
  let o = unlines . map reverse . lines $ i
  writeFile "output" o

Issues and pitfalls

• Debugging
• Lazy IO gotchas
  • File handles
  • Exceptions escaping
• Performance
  • Harder to understand and predict
  • Benchmarking
  • Performance cost to creating thunks
  • Space leaks
  • Too much laziness
  • Too little lazyness

Too much laziness

foldl  (+) 0 [1..100000]   -- 1,706,916 bytes max residency
foldl' (+) 0 [1..100000]   -- 3,732     bytes max residency

Enabling strictness analysis optimization with -O2, make foldl behave as foldl'.

Too little laziness

f :: Show a => [a] -> String
f = ("Report\n" ++) . unlines . map show

if length xs > 0 then f (tail xs) else f xs

if not (null xs) then f (tail xs) else f xs

f $ if not (null xs) then tail xs else xs