8.2 KiB
8.2 KiB
Iterator Pattern
Problem
You need to generate and iterate over a Fibonacci sequence without computing all values upfront (which could be infinite). Exposing the internal state of the generator couples consumers to implementation details. Different consumers may want to iterate in different ways (for-loops, manual stepping).
Solution
Provide a standard iteration protocol that lets consumers pull values one at a time from a generator. Each language has its own idiomatic approach: Python uses __iter__/__next__, Go uses closures, and JavaScript uses Symbol.iterator/generators.
Key participants:
- Iterator — provides
next()to get the next element - Iterable — provides a method to obtain an iterator
- Client — consumes values without knowing how they're generated
When to Use
- You need lazy evaluation — values computed on demand
- The collection is very large or infinite
- You want a uniform way to traverse different data structures
- You want to decouple traversal logic from the data structure
When to Avoid
- The collection is small and fully materialized — just use a slice/array
- You need random access (iterators are sequential by nature)
- The overhead of the iterator protocol is measurable for tight loops with trivial elements
Pseudocode
CLASS FibonacciIterator:
a = 0, b = 1
count, max
method has_next():
RETURN count < max
method next():
value = a
a, b = b, a + b
count += 1
RETURN value
// Usage:
fib = FibonacciIterator(max=10)
WHILE fib.has_next():
PRINT fib.next()
Python
Uses the __iter__/__next__ protocol so the class works directly with for loops.
from __future__ import annotations
class Fibonacci:
"""Iterable that produces Fibonacci numbers."""
def __init__(self, count: int) -> None:
self.count = count
def __iter__(self) -> FibonacciIterator:
return FibonacciIterator(self.count)
class FibonacciIterator:
"""Iterator that lazily computes Fibonacci values."""
def __init__(self, count: int) -> None:
self.count = count
self.index = 0
self.a = 0
self.b = 1
def __iter__(self) -> FibonacciIterator:
return self
def __next__(self) -> int:
if self.index >= self.count:
raise StopIteration
value = self.a
self.a, self.b = self.b, self.a + self.b
self.index += 1
return value
def fib_generator(count: int):
"""Alternative: Python generator function."""
a, b = 0, 1
for _ in range(count):
yield a
a, b = b, a + b
def main() -> None:
print("=== Class-based iterator (for loop) ===")
for num in Fibonacci(10):
print(num, end=" ")
print()
print("\n=== Manual iteration ===")
it = iter(Fibonacci(5))
while True:
try:
val = next(it)
print(f" Got: {val}")
except StopIteration:
print(" Done!")
break
print("\n=== Generator function ===")
for num in fib_generator(10):
print(num, end=" ")
print()
print("\n=== Multiple independent iterators ===")
fib = Fibonacci(6)
iter1 = iter(fib)
iter2 = iter(fib)
print(f" iter1: {next(iter1)}, {next(iter1)}, {next(iter1)}")
print(f" iter2: {next(iter2)}, {next(iter2)}")
if __name__ == "__main__":
main()
Output:
=== Class-based iterator (for loop) ===
0 1 1 2 3 5 8 13 21 34
=== Manual iteration ===
Got: 0
Got: 1
Got: 1
Got: 2
Got: 3
Done!
=== Generator function ===
0 1 1 2 3 5 8 13 21 34
=== Multiple independent iterators ===
iter1: 0, 1, 1
iter2: 0, 1
Go
Go uses closures to create iterator functions. There's no built-in iterator protocol, so a closure returning (value, bool) is idiomatic.
package main
import "fmt"
// NewFibonacci returns a closure that produces Fibonacci numbers.
// Each call returns the next value and whether the sequence continues.
func NewFibonacci(count int) func() (int, bool) {
a, b := 0, 1
index := 0
return func() (int, bool) {
if index >= count {
return 0, false
}
value := a
a, b = b, a+b
index++
return value, true
}
}
// FibonacciSlice is the pull-all-at-once alternative for comparison.
func FibonacciSlice(count int) []int {
result := make([]int, 0, count)
a, b := 0, 1
for i := 0; i < count; i++ {
result = append(result, a)
a, b = b, a+b
}
return result
}
// FibonacciChannel uses a channel for concurrent iteration.
func FibonacciChannel(count int) <-chan int {
ch := make(chan int)
go func() {
a, b := 0, 1
for i := 0; i < count; i++ {
ch <- a
a, b = b, a+b
}
close(ch)
}()
return ch
}
func main() {
fmt.Println("=== Closure-based iterator ===")
next := NewFibonacci(10)
for {
val, ok := next()
if !ok {
break
}
fmt.Printf("%d ", val)
}
fmt.Println()
fmt.Println("\n=== Slice-based (eager) ===")
for _, v := range FibonacciSlice(10) {
fmt.Printf("%d ", v)
}
fmt.Println()
fmt.Println("\n=== Channel-based iterator ===")
for v := range FibonacciChannel(10) {
fmt.Printf("%d ", v)
}
fmt.Println()
fmt.Println("\n=== Two independent iterators ===")
iter1 := NewFibonacci(6)
iter2 := NewFibonacci(6)
v1, _ := iter1()
v2, _ := iter1()
v3, _ := iter1()
fmt.Printf(" iter1: %d, %d, %d\n", v1, v2, v3)
v1, _ = iter2()
v2, _ = iter2()
fmt.Printf(" iter2: %d, %d\n", v1, v2)
}
Output:
=== Closure-based iterator ===
0 1 1 2 3 5 8 13 21 34
=== Slice-based (eager) ===
0 1 1 2 3 5 8 13 21 34
=== Channel-based iterator ===
0 1 1 2 3 5 8 13 21 34
=== Two independent iterators ===
iter1: 0, 1, 1
iter2: 0, 1
JavaScript
Uses Symbol.iterator protocol and generator functions for idiomatic iteration.
class Fibonacci {
constructor(count) {
this.count = count;
}
[Symbol.iterator]() {
let a = 0;
let b = 1;
let index = 0;
const max = this.count;
return {
next() {
if (index >= max) {
return { value: undefined, done: true };
}
const value = a;
[a, b] = [b, a + b];
index++;
return { value, done: false };
},
};
}
}
// Generator function alternative
function* fibGenerator(count) {
let a = 0;
let b = 1;
for (let i = 0; i < count; i++) {
yield a;
[a, b] = [b, a + b];
}
}
// --- Demo ---
console.log("=== Symbol.iterator (for...of) ===");
const values = [];
for (const num of new Fibonacci(10)) {
values.push(num);
}
console.log(values.join(" "));
console.log("\n=== Manual iteration ===");
const iter = new Fibonacci(5)[Symbol.iterator]();
let result = iter.next();
while (!result.done) {
console.log(` Got: ${result.value}`);
result = iter.next();
}
console.log(" Done!");
console.log("\n=== Generator function ===");
const genValues = [];
for (const num of fibGenerator(10)) {
genValues.push(num);
}
console.log(genValues.join(" "));
console.log("\n=== Spread operator ===");
console.log([...new Fibonacci(10)].join(" "));
console.log("\n=== Destructuring ===");
const [first, second, third] = new Fibonacci(10);
console.log(`First three: ${first}, ${second}, ${third}`);
console.log("\n=== Two independent iterators ===");
const fib = new Fibonacci(6);
const iter1 = fib[Symbol.iterator]();
const iter2 = fib[Symbol.iterator]();
console.log(` iter1: ${iter1.next().value}, ${iter1.next().value}, ${iter1.next().value}`);
console.log(` iter2: ${iter2.next().value}, ${iter2.next().value}`);
Output:
=== Symbol.iterator (for...of) ===
0 1 1 2 3 5 8 13 21 34
=== Manual iteration ===
Got: 0
Got: 1
Got: 1
Got: 2
Got: 3
Done!
=== Generator function ===
0 1 1 2 3 5 8 13 21 34
=== Spread operator ===
0 1 1 2 3 5 8 13 21 34
=== Destructuring ===
First three: 0, 1, 1
=== Two independent iterators ===
iter1: 0, 1, 1
iter2: 0, 1
Related Patterns
- Composite — iterators commonly traverse composite tree structures.
- Visitor — visitor and iterator are often combined: iterator traverses, visitor operates on each element.
- Lazy Evaluation — generators are the lazy-evaluation form of iterators.
- Generator — a generator function is the idiomatic way to implement an iterator in Python/JavaScript.