0101: Email Tutorials ‐ Lazy Evaluation

FP14 Graham Hutton Video

📚 Table of Contents

1. Email 101 – How Haskell Programs Are Executed
2. Email 92 – What Is Lazy Evaluation?
3. Email 93 – Benefits of Lazy Evaluation
4. Email 94 – Evaluation by Applying Definitions
5. Email 95 – Innermost vs Outermost Evaluation
6. Email 96 – Termination and Infinite Computations
7. Email 97 – Sharing and the Meaning of Laziness
8. Email 98 – Infinite Lists in Practice
9. Email 99 – Modular Programming with Lazy Evaluation
10. Email 100 – Prime Numbers and the Sieve of Eratosthenes
11. Glossary of Terms
12. Quiz Questions (Table Format)
13. Quiz Options (Table Format)
14. Next Steps and Quiz Link

Email 101 – How Haskell Programs Are Executed

Up until now in the course, the focus has been on writing programs that are clear, concise, and correct. These are the three C’s that have guided every example so far.

However, one important question has not yet been addressed: how are Haskell programs actually executed? This final lecture introduces the execution model used by Haskell, which is known as lazy evaluation.

Rather than evaluating everything immediately, Haskell delays computation until the result is actually required. This execution strategy turns out to have several powerful consequences.

Email 92 – What Is Lazy Evaluation?

Lazy evaluation is the technique used by Haskell to evaluate expressions. Instead of eagerly computing values as soon as they appear, expressions are evaluated only when their results are needed.

This means that Haskell avoids unnecessary work. If part of a program’s result is never used, that computation is never performed.

Email 93 – Benefits of Lazy Evaluation

Lazy evaluation provides four key benefits.

First, it avoids unnecessary computation, which can improve efficiency. Second, it ensures termination whenever possible, meaning that if any evaluation order can produce a result, lazy evaluation will find it. Third, it enables programming with infinite lists and infinite data structures. Finally, it allows programs to be written in a more modular way by separating control from data.

Email 94 – Evaluation by Applying Definitions

The most basic way to evaluate expressions is by repeatedly applying definitions until no further simplification is possible. This is familiar from school mathematics.

For example, if square n = n * n, then evaluating square (1 + 2) can be done by first computing 1 + 2 or by expanding the definition of square. Both approaches lead to the same result.

Email 95 – Innermost vs Outermost Evaluation

There are two extreme evaluation strategies.

Innermost evaluation reduces the smallest expressions first. Outermost evaluation reduces the largest expressions first.

In a pure functional language like Haskell, all evaluation orders give the same result provided they terminate. The difference lies in whether they terminate and how much work they perform.

Email 96 – Termination and Infinite Computations

Consider a recursive definition such as infinity = 1 + infinity. Using innermost evaluation, expressions involving infinity may never terminate.

However, with outermost evaluation, it is sometimes possible to obtain a result without fully expanding infinite structures. This means outermost evaluation may terminate even when innermost evaluation does not.

Email 97 – Sharing and the Meaning of Laziness

Outermost evaluation can duplicate work. Lazy evaluation fixes this by sharing results instead of recomputing them.

Lazy evaluation is therefore defined as outermost evaluation combined with sharing. This ensures termination whenever possible and never requires more steps than innermost evaluation.

Email 98 – Infinite Lists in Practice

Lazy evaluation makes infinite lists practical. For example, the list ones = 1 : ones represents a potentially infinite list.

If a program only needs the first element, only that element is produced. The rest of the list is never evaluated.

This is why infinite lists in Haskell are potentially infinite rather than immediately infinite.

Email 99 – Modular Programming with Lazy Evaluation

Lazy evaluation enables a powerful form of modular programming.

Programs can be split into a data-producing part and a control part. For example, an infinite list of values can be combined with a control function such as take.

This separation makes programs clearer, more reusable, and more expressive.

Email 100 – Prime Numbers and the Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for generating prime numbers. Using lazy evaluation, it can be implemented as a short and elegant Haskell program.

The infinite list of prime numbers is defined once, and different control functions determine how many primes are used. This includes generating the first ten primes, primes below a threshold, or even twin primes.

📘 Glossary of Terms

Lazy Evaluation An evaluation strategy where expressions are evaluated only when their results are required.

Innermost Evaluation An evaluation strategy that reduces the smallest expressions first.

Outermost Evaluation An evaluation strategy that reduces the largest expressions first.

Infinite List A list defined recursively that can produce values indefinitely when needed.

Sharing A technique where evaluated expressions are reused instead of recomputed.

Sieve of Eratosthenes An algorithm for generating prime numbers by repeatedly removing multiples.

📖 Recommended Reading

Buy Book

🎓 Final Step: Quiz & Progress Badge

Quizz & Progress Badge NFT