Evaluation Strategies

Evaluation strategies determine when expressions are evaluated during program execution. Haskell uses lazy evaluation by default, which has significant implications for how programs behave.

Lazy vs. Eager Evaluation

Eager (Strict) Evaluation

In eager (strict) evaluation:

Arguments to functions are evaluated before the function is called
Expressions are evaluated as soon as they are bound to variables
Most common programming languages (C, Java, Python, etc.) use eager evaluation

Example in Python (eager):

def f(x, y):
    return x + 2
 
# Both arguments are evaluated, even though y is never used
result = f(3, expensive_computation())

Lazy (Non-strict) Evaluation

In lazy (non-strict) evaluation:

Expressions are only evaluated when their values are needed
Arguments to functions are not evaluated until they are used inside the function
Evaluation is delayed until the last possible moment (“call by need”)

Example in Haskell (lazy):

f :: Int -> Int -> Int
f x y = x + 2
 
-- y is never evaluated because it's not used in the function body
result = f 3 (expensive_computation)

Benefits of Lazy Evaluation

Infinite Data Structures

Lazy evaluation allows for infinite data structures:

-- Infinite list of natural numbers
naturals = [0..]
 
-- We can operate on infinite lists
take 5 naturals                  -- [0,1,2,3,4]
take 10 (filter even naturals)   -- [0,2,4,6,8,10,12,14,16,18]

Short-Circuit Evaluation

Functions can terminate early without evaluating all arguments:

-- Returns first element of the list that satisfies the predicate
find :: (a -> Bool) -> [a] -> Maybe a
find p [] = Nothing
find p (x:xs)
  | p x       = Just x       -- Terminates here if predicate is satisfied
  | otherwise = find p xs
  
-- Only computes until it finds the first prime number greater than 100
find (> 100) primes

Performance Optimization

Lazy evaluation can lead to performance optimizations:

Avoiding unnecessary computations:
```
if condition then expensiveComputation1 else expensiveComputation2
```
Only one of the expensive computations will be evaluated, depending on the condition.
Fusion transformations:
```
sum (map (*2) [1..1000000])
```
Can be optimized to avoid creating the intermediate list.

Better Modularity

Lazy evaluation allows for better separation of concerns:

-- Producer generates all possible solutions
solutions = generateAllPossibleSolutions problem
 
-- Consumer takes only what it needs
firstSolution = head solutions
bestSolution = minimumBy compareCost solutions

Drawbacks of Lazy Evaluation

Unpredictable Space Usage

Lazy evaluation can lead to space leaks if thunks (unevaluated expressions) build up:

sum [1..1000000]  -- Can use a lot of memory due to thunk accumulation

Harder to Reason About Performance

It can be difficult to predict exactly when expressions will be evaluated.

Not Always More Efficient

For code that needs to evaluate everything anyway, the overhead of tracking thunks can make lazy evaluation less efficient.

Thunks

A thunk is a suspended computation - a promise to compute a value when needed.

Thunks are created when expressions are not immediately evaluated
They store all data needed to evaluate the expression later
When evaluation is needed, the thunk is forced and replaced with the result

Forcing Evaluation

Bang Patterns

Bang patterns (!) can be used to force evaluation:

-- This version of sum is strict in its accumulator
sum' :: [Int] -> Int
sum' = go 0
  where
    go !acc [] = acc
    go !acc (x:xs) = go (acc + x) xs

Seq Function

The seq function forces evaluation of its first argument before returning the second:

seq :: a -> b -> b
 
-- Forces evaluation of x before returning y
x `seq` y

Example usage:

sum' :: [Int] -> Int
sum' xs = go 0 xs
  where
    go acc [] = acc
    go acc (x:xs) = let acc' = acc + x in acc' `seq` go acc' xs

Strictness Annotations

Data types can be made strict with strictness annotations:

data Pair a b = Pair !a !b

This forces both fields to be evaluated when the constructor is evaluated.

Common Patterns

Lazy Functions vs. Strict Data

A common pattern in Haskell is to write functions that are lazy in their arguments but strict in their data fields:

data Vector = Vector !Double !Double !Double
 
dot :: Vector -> Vector -> Double
dot (Vector x1 y1 z1) (Vector x2 y2 z2) = x1*x2 + y1*y2 + z1*z2

Worker/Wrapper Transformation

For recursive functions, a common pattern is to have a lazy wrapper function and a strict worker function:

sum :: [Int] -> Int
sum = sum' 0  -- Lazy wrapper
  where
    sum' !acc [] = acc  -- Strict worker
    sum' !acc (x:xs) = sum' (acc + x) xs

Examples of Infinite Structures

Infinite Lists

-- Infinite list of ones
ones = 1 : ones
 
-- Infinite list of Fibonacci numbers
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 
-- Primes using the Sieve of Eratosthenes
primes = sieve [2..]
  where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

Infinite Trees

data Tree a = Node a (Tree a) (Tree a)
 
-- Infinite binary tree where each node contains its path
paths = build []
  where build path = Node path (build (False:path)) (build (True:path))

Key Points to Remember

Haskell uses lazy evaluation by default: expressions are only evaluated when needed
Lazy evaluation enables infinite data structures and certain programming patterns
Thunks are delayed computations that are evaluated on demand
Strict evaluation can be enforced using bang patterns, seq, or strictness annotations
Space leaks are a common issue with lazy evaluation, requiring careful attention to performance

Quartz 4

Explorer