Skip to content

An iterator is lazy

Level: 201 · anyone who has written a function that returns a slice and wondered how big to make it

One line: An iterator makes each element when the loop asks for it, so an infinite Naturals is fine to range over with a break, Filter and Take compose without building a slice, and a produced counter shows the producer made exactly as many elements as the loop consumed — where a function returning []int has to be told its length up front and does all the work before the caller sees the first element.

Naturals yields 1, 2, 3, … for ever, counting each element in produced. Filter and Take are adapters: each takes an iter.Seq and returns one. main ranges over Naturals with a break, builds a pipeline of the multiples of seven and the first four of those, checks the counter before and after ranging over it, and for contrast calls firstSquares, the slice version.

Verified output of an_iterator_is_lazy_go.go — regenerated by tools/run_examples.py, never hand-typed.

-- range over an infinite sequence, with a break
loop: got 1
loop: got 2
loop: got 3
produced: 4
-- compose Filter and Take: nothing runs until the range
built the pipeline; produced: 0
loop: got 7
loop: got 14
loop: got 21
loop: got 28
produced: 28
-- a slice has to know its length up front
firstSquares(4): [1 4 9 16]

Reading the output

produced: 4 after three values. The loop asked for a fourth element, saw it was over 3, and broke. Naturals made four numbers — the three printed and the one the loop rejected — and nothing beyond, because break makes yield return false and the producer returned. An infinite sequence costs only what is consumed.

built the pipeline; produced: 0. Filter(Naturals, …) and Take(…, 4) returned closures; calling them ran no loop and touched no element. Nothing happens until something ranges over firstFour. The Rust library's Iterators are lazy ↗ says the same about map and filter there: an adapter is a description of work, and a consumer is what runs it.

produced: 28 for four multiples of seven. Each element went from Naturals through Filter's yield, through Take's yield, to the loop body, one at a time, on one goroutine. After the fourth accepted element Take returned, which made Filter's call to yield return false, which made Filter return, which made Naturals' call to yield return false. Twenty-eight numbers were made and no slice of any length existed.

firstSquares(4) is the slice version. It has to be told 4, it computes all four before returning, and a caller that only wanted the first square over 10 has no way to stop it. It can never be infinite. For four squares that is nothing; for a table scan or a file it is the whole cost.

The shape is a pipeline, without the goroutines. A pipeline of stages builds Filter and Take from goroutines and channels, and pays for them: a goroutine per stage, a channel operation per element, a close or a cancellation to shut down. Iterator adapters are function calls on the loop's own goroutine — no concurrency, which also means no parallelism and no way for a stage to run ahead.

an_iterator_is_lazy_go.go

an_iterator_is_lazy_go.go in full — pasted here by tools/run_examples.py from the file CI runs.

// An iterator makes each element when the loop asks for it, so an infinite
// sequence is fine to range over, and Filter and Take compose without ever
// building a slice. A counter says how many elements the producer made.
//
//  go build an_iterator_is_lazy_go.go && ./an_iterator_is_lazy_go
package main

import (
    "fmt"
    "iter"
)

// produced counts every element Naturals handed to yield.
var produced int

// Naturals yields 1, 2, 3, ... for as long as the loop wants them.
func Naturals(yield func(int) bool) {
    for n := 1; ; n++ {
        produced++
        if !yield(n) {
            return
        }
    }
}

// Filter yields the elements of seq that keep accepts. Nothing runs until
// the returned iterator is ranged over.
func Filter[V any](seq iter.Seq[V], keep func(V) bool) iter.Seq[V] {
    return func(yield func(V) bool) {
        for v := range seq {
            if keep(v) && !yield(v) {
                return
            }
        }
    }
}

// Take yields at most n elements of seq, then stops asking seq for more.
func Take[V any](seq iter.Seq[V], n int) iter.Seq[V] {
    return func(yield func(V) bool) {
        if n <= 0 {
            return
        }
        taken := 0
        for v := range seq {
            if !yield(v) {
                return
            }
            taken++
            if taken == n {
                return
            }
        }
    }
}

// firstSquares is the slice version: it has to be told how many to make, and
// makes all of them before the caller sees the first.
func firstSquares(n int) []int {
    squares := make([]int, 0, n)
    for i := 1; i <= n; i++ {
        squares = append(squares, i*i)
    }
    return squares
}

func main() {
    fmt.Println("-- range over an infinite sequence, with a break")
    for n := range Naturals {
        if n > 3 {
            break
        }
        fmt.Println("loop: got", n)
    }
    fmt.Println("produced:", produced)

    fmt.Println("-- compose Filter and Take: nothing runs until the range")
    produced = 0
    multiplesOfSeven := Filter(Naturals, func(n int) bool { return n%7 == 0 })
    firstFour := Take(multiplesOfSeven, 4)
    fmt.Println("built the pipeline; produced:", produced)
    for n := range firstFour {
        fmt.Println("loop: got", n)
    }
    fmt.Println("produced:", produced)

    fmt.Println("-- a slice has to know its length up front")
    fmt.Println("firstSquares(4):", firstSquares(4))
}

What to do

  • Return an iter.Seq rather than a slice when the caller may stop early, when the sequence has no natural end, or when each element is expensive to make. Return a slice when the caller needs the length, an index, or a second pass.
  • Write adapters as functions from Seq to Seq, generic over the element type (A type parameter needs a constraint), and make each one stop asking its source for elements the moment its own yield returns false — Take above returns after its fourth, and that return is what stops Naturals.
  • Collect only at the edge, with slices.Collect, when a slice is what the next step needs.
  • Laziness is not concurrency. Nothing in the pipeline runs before the loop asks, and a stage that blocks blocks the loop. A stage that should run ahead, or in parallel, is a goroutine and a channel.

Practice

Write Fibonacci as an infinite iter.Seq[int] with a produced counter, and TakeWhile(seq iter.Seq[V], keep func(V) bool) iter.Seq[V] that stops at the first element keep rejects. Print the Fibonacci numbers below 100, and show that the producer made exactly one number more than was printed — the one TakeWhile rejected.

Solution

an_iterator_is_lazy_kata_go.go in full — pasted here by tools/run_examples.py from the file CI runs.

// Kata: an infinite Fibonacci iterator, a TakeWhile adapter, and a counter
// that shows the producer made exactly one number more than was printed.
//
//  go build an_iterator_is_lazy_kata_go.go && ./an_iterator_is_lazy_kata_go
package main

import (
    "fmt"
    "iter"
)

// produced counts every number Fibonacci handed to yield.
var produced int

// Fibonacci yields 1, 1, 2, 3, 5, ... without end.
func Fibonacci(yield func(int) bool) {
    a, b := 1, 1
    for {
        produced++
        if !yield(a) {
            return
        }
        a, b = b, a+b
    }
}

// TakeWhile yields elements of seq until keep rejects one, then stops seq.
func TakeWhile[V any](seq iter.Seq[V], keep func(V) bool) iter.Seq[V] {
    return func(yield func(V) bool) {
        for v := range seq {
            if !keep(v) || !yield(v) {
                return
            }
        }
    }
}

func main() {
    var below100 []int
    for n := range TakeWhile(Fibonacci, func(n int) bool { return n < 100 }) {
        below100 = append(below100, n)
    }
    fmt.Println(below100)
    fmt.Printf("printed %d numbers; the producer made %d\n", len(below100), produced)
}

Verified output of an_iterator_is_lazy_kata_go.go — regenerated by tools/run_examples.py, never hand-typed.

[1 1 2 3 5 8 13 21 34 55 89]
printed 11 numbers; the producer made 12

In other languages

  • The Rust library's Iterators are lazy ↗ and Collect the iterator into a Vec ↗ — the same two ideas, with Rust's take and filter as methods on the iterator rather than free functions. Rust also has Adapters by job ↗, twenty-odd of them in the standard library; Go 1.25 ships none beyond what slices and maps need, and the proposal for an xiter package of adapters was declined (Resources).
  • Python's itertools ↗ — itertools.count() is Naturals, itertools.islice is Take, filter is Filter, and a generator expression is lazy in the same way. list(...) is slices.Collect.

Sources