Lazy Streams: Haskell vs. Python Generators

Hello! Welcome to your fourth lesson in the module on Evaluation Strategies.

Introduction

In our last lesson, we analyzed how a language's evaluation strategy—strict vs. lazy—profoundly affects program termination, error handling, and the management of side effects. We concluded with a key insight: lazy evaluation is the mechanism that makes it practical to define and work with infinite data structures.

Today, we will build directly on that foundation. Our goal is to:

Implement and process infinite data structures (streams) using lazy evaluation, comparing Haskell's native support with Python's generators.

We will explore this concept from two angles:

1. Haskell: A language where laziness is the default and infinite lists are a natural, idiomatic feature.
2. Python: A language that is eager by default but provides powerful tools—namely generators—to simulate lazy evaluation and work with infinite sequences.

By the end of this lesson, you'll understand not just the "how" but also the "why" behind these two different approaches to the same powerful idea.

1. The Native Approach: Infinite Lists in Haskell

In Haskell, laziness is not an add-on; it's the default evaluation model. This means that any data structure, including lists, is evaluated on demand. An "infinite list" is simply a list where the tail is an unevaluated expression—a thunk—that holds the recipe for computing the rest of the list when needed.

This video provides an excellent introduction to how this works in practice.

How It Works: Thunks

As the video explained, the magic behind this is lazy evaluation. When you define numbers = [1..], Haskell doesn't generate a billion numbers. It creates a data structure in memory that looks something like this:

numbers -> (1 : <thunk for [2..]>)

The list is a cons cell containing the head (1) and a thunk (a placeholder for a computation) for the tail. Only when you ask for the second element, say with take 2 numbers, does Haskell evaluate the thunk. This evaluation produces another cons cell and another thunk:

numbers -> (1 : (2 : <thunk for [3..]>))

The Sieve of Eratosthenes example is particularly telling. The Haskell code is a direct, declarative translation of the algorithm's description, operating on streams:

-- The infinite list of primes is the result of sieving
-- the infinite list of integers starting from 2.
primes = sieve [2..]

-- To sieve a stream (p:xs):
--   - p is the first prime.
--   - The rest of the primes are found by sieving the rest of the stream (xs),
--     after filtering out all multiples of p.
sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs)

This recursive definition on an infinite list is only possible because of laziness. A strict language would enter an infinite loop trying to evaluate [2..] or the filter operation on it.

2. The Simulated Approach: Generators in Python

Python is a strict (eager) language. If you try [i for i in range(1, float('inf'))], your program will hang and exhaust all memory. To achieve laziness, Python uses the iterator protocol. A special kind of iterator, perfect for defining lazy sequences, is a generator.

A generator is a function that uses the yield keyword to produce a sequence of values over time, pausing its execution state between each value.

This next video provides a comprehensive overview of generators.

Creating and Using Infinite Sequences in Python

As the video showed, we can create infinite sequences using a generator function with an infinite loop.

# An infinite sequence of natural numbers
def naturals():
    n = 0
    while True:
        yield n
        n += 1

# An infinite sequence of repeated values
def repeat(value):
    while True:
        yield value

When you call naturals(), the code doesn't run. You get a generator object.

>>> nums = naturals()
>>> nums
<generator object naturals at 0x...>

The values are only produced when you iterate over it, for example, by calling next():

>>> next(nums)
0
>>> next(nums)
1

This is Python's explicit way of achieving the "evaluate-on-demand" behavior that is implicit in Haskell.

To learn more about how Python's standard library supports this, please read the following short text.

3. A Direct Comparison: The Sieve of Eratosthenes

Now, let's put it all together by comparing the implementation of the Sieve of Eratosthenes in both languages. This will crystallize the differences in their approaches.

Let's analyze the two Sieve implementations from the article.

Haskell:

sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs)
primes = sieve [2..]

• Declarative: The code reads like a mathematical definition.
• Implicit Laziness: The entire mechanism relies on the fact that [2..], filter, and the recursive call to sieve are all lazy. The data flows through the chain of functions as needed.
• Concise: The syntax for list manipulation and function application is extremely compact.

Python:

def filter_out_divisible_by(p, xs):
    for x in xs:
        if x % p != 0:
            yield x

def sieve(xs):
    p = next(xs)
    yield p
    yield from sieve(filter_out_divisible_by(p, xs))

def primes():
    yield from sieve(itertools.count(2))

• Imperative/Explicit: The code is more explicit about the process. We use a for loop, if statements, and the yield keyword to control the flow of data.
• Explicit Laziness: Laziness is achieved through the generator protocol. sieve pulls a value p from the stream, yields it, and then recursively constructs a new generator for the rest of the stream.
• Verbose: It requires more lines and explicit function definitions to achieve the same logic. The yield from syntax (similar to await in async programming) helps, but it's still more verbose than Haskell's : operator.

Summary of Comparison

Feature	Haskell (Native Laziness)	Python (Simulated Laziness)
Mechanism	Default lazy evaluation (call-by-need). Data structures are built of values and thunks.	The iterator protocol. Generators are functions that pause and resume execution (yield).
Syntax	[1..], x : xs (cons), function composition.	itertools.count(), yield, yield from, generator expressions.
Default	Lazy by default. Eagerness is opt-in (e.g., using seq).	Eager by default. Laziness is opt-in via generators/iterators.
Composition	Functions operating on lists compose naturally. take 10 . filter odd $ [1..]	Functions are chained into pipelines. islice((x for x in count(1) if x % 2 != 0), 10)
Mindset	"Define the entire infinite thing, then take what you need."	"Define a recipe for producing values one by one."

Conclusion

Today we explored two powerful ways to work with infinite data structures. While the end result is similar—the ability to process sequences of unbounded length with finite memory—the paths taken by Haskell and Python reveal a core philosophical difference in language design.

Key Takeaways:

• Infinite data structures, or streams, are a powerful abstraction made possible by lazy evaluation.
• Haskell embraces laziness by default, leading to an elegant and declarative style where infinite lists are first-class citizens.
• Python, an eager language, simulates laziness explicitly using generators and the iterator protocol, providing a more imperative but still highly effective way to build data processing pipelines.
• The core concept in both is the separation of data generation from data consumption. You define the "what" (the infinite sequence) independently of the "how much" (the part you actually compute).

Preview of the Next Lesson:

We've now seen how evaluation strategy and purity are deeply intertwined, and how they enable concepts like infinite data structures. We're going to shift gears from how code is evaluated to what kind of data it can operate on. This brings us to the next major topic in programming language theory: type systems.

In our next lesson, we will begin Module 4 by addressing the learning outcome: "Distinguish static typing from dynamic typing, referencing their historical origins in the Fortran/ALGOL vs. Lisp traditions." We'll explore the fundamental trade-offs between checking types at compile-time versus run-time.