Lazy pagination

A plain def containing yield is already a generator -- there is no separate type to declare and no interface to satisfy. for item in items() pulls one value at a time, and the break in the consumer simply stops pulling.

"""Lazy pagination: walk every item across pages, fetching a page only when
the consumer actually needs an item from it."""
from typing import Iterator

PAGES = [
    ["alpha", "beta", "gamma", "delta"],
    ["epsilon", "zeta", "eta", "theta"],
    ["iota", "kappa", "lambda", "mu"],
]


def fetch_page(n: int) -> tuple[list[str], bool]:
    """Stands in for an API call. Prints so laziness is visible, not claimed."""
    print(f"fetch page {n}")
    return PAGES[n - 1], n < len(PAGES)


def items() -> Iterator[str]:
    """A generator: `yield` suspends here and resumes on the next request,
    so the loop below never runs ahead of what the consumer asked for."""
    page = 1
    while True:
        batch, has_more = fetch_page(page)
        for item in batch:
            yield item
        if not has_more:
            return
        page += 1


def main() -> None:
    taken = 0
    for item in items():
        print(item)
        taken += 1
        if taken == 6:
            break
    print(f"--- took {taken} items, fetched 2 of {len(PAGES)} pages")


if __name__ == "__main__":
    main()

function* is the same idea with a sigil. The break matters more than it looks: it calls the generator's return(), which runs any finally blocks -- the generator is told it is being abandoned.

// Lazy pagination: walk every item across pages, fetching a page only when
// the consumer actually needs an item from it.
const PAGES = [
  ["alpha", "beta", "gamma", "delta"],
  ["epsilon", "zeta", "eta", "theta"],
  ["iota", "kappa", "lambda", "mu"],
];

// Stands in for an API call. Prints so laziness is visible, not claimed.
function fetchPage(n) {
  console.log(`fetch page ${n}`);
  return { batch: PAGES[n - 1], hasMore: n < PAGES.length };
}

// A generator: `yield` suspends here and resumes on the next request, so the
// loop never runs ahead of what the consumer asked for.
function* items() {
  let page = 1;
  for (;;) {
    const { batch, hasMore } = fetchPage(page);
    for (const item of batch) yield item;
    if (!hasMore) return;
    page += 1;
  }
}

let taken = 0;
for (const item of items()) {
  console.log(item);
  taken += 1;
  if (taken === 6) break;        // break closes the generator
}
console.log(`--- took ${taken} items, fetched 2 of ${PAGES.length} pages`);

Identical machinery to JavaScript; Generator<string> only names what comes out. Worth seeing precisely because it is unchanged: types describe the sequence, they do not produce it.

// Lazy pagination: walk every item across pages, fetching a page only when
// the consumer actually needs an item from it.
const PAGES: string[][] = [
  ["alpha", "beta", "gamma", "delta"],
  ["epsilon", "zeta", "eta", "theta"],
  ["iota", "kappa", "lambda", "mu"],
];

interface Page {
  batch: string[];
  hasMore: boolean;
}

// Stands in for an API call. Prints so laziness is visible, not claimed.
function fetchPage(n: number): Page {
  console.log(`fetch page ${n}`);
  return { batch: PAGES[n - 1], hasMore: n < PAGES.length };
}

// Generator<string> types what comes out; the machinery is JavaScript's.
function* items(): Generator<string> {
  let page = 1;
  for (;;) {
    const { batch, hasMore }: Page = fetchPage(page);
    for (const item of batch) yield item;
    if (!hasMore) return;
    page += 1;
  }
}

let taken = 0;
for (const item of items()) {
  console.log(item);
  taken += 1;
  if (taken === 6) break;
}
console.log(`--- took ${taken} items, fetched 2 of ${PAGES.length} pages`);

sequence { } is a restricted coroutine. It reads like Python, but it is a library feature built on suspension rather than a keyword in the grammar -- yield here is a method call on a scope receiver.

// Lazy pagination: walk every item across pages, fetching a page only when
// the consumer actually needs an item from it.
val PAGES = listOf(
    listOf("alpha", "beta", "gamma", "delta"),
    listOf("epsilon", "zeta", "eta", "theta"),
    listOf("iota", "kappa", "lambda", "mu"),
)

/** Stands in for an API call. Prints so laziness is visible, not claimed. */
fun fetchPage(n: Int): Pair<List<String>, Boolean> {
    println("fetch page $n")
    return Pair(PAGES[n - 1], n < PAGES.size)
}

/**
 * `sequence { }` is a restricted coroutine: yield() suspends the builder and
 * resumes it when the consumer asks for the next value.
 */
fun items(): Sequence<String> = sequence {
    var page = 1
    while (true) {
        val (batch, hasMore) = fetchPage(page)
        for (item in batch) yield(item)
        if (!hasMore) return@sequence
        page += 1
    }
}

fun main() {
    var taken = 0
    // take(6) stays lazy -- the sequence is only pulled six times.
    for (item in items().take(6)) {
        println(item)
        taken += 1
    }
    println("--- took $taken items, fetched 2 of ${PAGES.size} pages")
}

Go inverts the whole thing. iter.Seq is a function that takes your loop body as a callback, so the producer is the caller. That is why yield returns a bool: false is the consumer's break arriving back in the producer, and ignoring it would be a bug.

// Lazy pagination: walk every item across pages, fetching a page only when
// the consumer actually needs an item from it.
package main

import (
	"fmt"
	"iter"
)

var pages = [][]string{
	{"alpha", "beta", "gamma", "delta"},
	{"epsilon", "zeta", "eta", "theta"},
	{"iota", "kappa", "lambda", "mu"},
}

// Stands in for an API call. Prints so laziness is visible, not claimed.
func fetchPage(n int) ([]string, bool) {
	fmt.Printf("fetch page %d\n", n)
	return pages[n-1], n < len(pages)
}

// iter.Seq is a function that takes a yield callback. Returning false from
// yield means the consumer stopped, so we stop too -- that is how `break`
// in a range loop reaches back into the producer.
func items() iter.Seq[string] {
	return func(yield func(string) bool) {
		for page := 1; ; page++ {
			batch, hasMore := fetchPage(page)
			for _, item := range batch {
				if !yield(item) {
					return
				}
			}
			if !hasMore {
				return
			}
		}
	}
}

func main() {
	taken := 0
	for item := range items() {
		fmt.Println(item)
		taken++
		if taken == 6 {
			break
		}
	}
	fmt.Printf("--- took %d items, fetched 2 of %d pages\n", taken, len(pages))
}

No yield, so the state machine is written out: which page, which index, whether the source is exhausted. In exchange, Items is an ordinary struct with no allocation and no indirection, and .take(6) composes onto it for free.

// Lazy pagination: walk every item across pages, fetching a page only when
// the consumer actually needs an item from it.
const PAGES: [[&str; 4]; 3] = [
    ["alpha", "beta", "gamma", "delta"],
    ["epsilon", "zeta", "eta", "theta"],
    ["iota", "kappa", "lambda", "mu"],
];

/// Stands in for an API call. Prints so laziness is visible, not claimed.
fn fetch_page(n: usize) -> (&'static [&'static str], bool) {
    println!("fetch page {}", n);
    (&PAGES[n - 1], n < PAGES.len())
}

/// The state machine is explicit and lives in the struct -- Rust has no
/// `yield`, so the compiler cannot write it for you.
struct Items {
    page: usize,
    batch: &'static [&'static str],
    index: usize,
    done: bool,
}

impl Items {
    fn new() -> Self {
        Items { page: 0, batch: &[], index: 0, done: false }
    }
}

impl Iterator for Items {
    type Item = &'static str;

    /// Called once per item. Everything between calls is held in `self`.
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if self.index < self.batch.len() {
                let item = self.batch[self.index];
                self.index += 1;
                return Some(item);
            }
            if self.done {
                return None;
            }
            self.page += 1;
            let (batch, has_more) = fetch_page(self.page);
            self.batch = batch;
            self.index = 0;
            self.done = !has_more;
        }
    }
}

fn main() {
    let mut taken = 0;
    // `take(6)` is itself lazy: it only pulls six times.
    for item in Items::new().take(6) {
        println!("{}", item);
        taken += 1;
    }
    println!("--- took {} items, fetched 2 of {} pages", taken, PAGES.len());
}

The state machine again, but split across two methods, and that split is the interesting part. hasNext() has to be callable twice without consuming anything, so the fetch has to happen there rather than in next() -- the contract shapes the code.

// Lazy pagination: walk every item across pages, fetching a page only when
// the consumer actually needs an item from it.
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class Paginate {

    static final List<List<String>> PAGES = List.of(
            List.of("alpha", "beta", "gamma", "delta"),
            List.of("epsilon", "zeta", "eta", "theta"),
            List.of("iota", "kappa", "lambda", "mu"));

    /** One page of results, plus whether another page exists. */
    record Page(List<String> batch, boolean hasMore) {}

    /** Stands in for an API call. Prints so laziness is visible, not claimed. */
    static Page fetchPage(int n) {
        System.out.println("fetch page " + n);
        return new Page(PAGES.get(n - 1), n < PAGES.size());
    }

    /**
     * Java has no `yield`, so the state machine is written by hand and lives in
     * the fields. hasNext() must be able to run twice without consuming, which
     * is why the fetch happens there rather than in next().
     */
    static class Items implements Iterator<String> {
        private int page = 0;
        private List<String> batch = List.of();
        private int index = 0;
        private boolean done = false;

        @Override
        public boolean hasNext() {
            while (index >= batch.size()) {
                if (done) return false;
                Page p = fetchPage(++page);
                batch = p.batch();
                index = 0;
                done = !p.hasMore();
            }
            return true;
        }

        @Override
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            return batch.get(index++);
        }
    }

    public static void main(String[] args) {
        int taken = 0;
        Iterator<String> it = new Items();
        while (taken < 6 && it.hasNext()) {
            System.out.println(it.next());
            taken++;
        }
        System.out.println("--- took " + taken + " items, fetched 2 of " + PAGES.size() + " pages");
    }
}

The same explicit state as Rust, plus the cost of making range-for work: an inner iterator type with operator*, operator++ and operator!=. Reaching the end is modelled by the iterator becoming null.

// Lazy pagination: walk every item across pages, fetching a page only when
// the consumer actually needs an item from it.
#include <array>
#include <iostream>
#include <string_view>

constexpr std::array<std::array<std::string_view, 4>, 3> PAGES{{
    {"alpha", "beta", "gamma", "delta"},
    {"epsilon", "zeta", "eta", "theta"},
    {"iota", "kappa", "lambda", "mu"},
}};

/// Stands in for an API call. Prints so laziness is visible, not claimed.
const std::array<std::string_view, 4>& fetch_page(int n, bool& has_more) {
    std::cout << "fetch page " << n << "\n";
    has_more = n < static_cast<int>(PAGES.size());
    return PAGES[n - 1];
}

/// No yield either, so the state lives in the class. Exposing begin()/end()
/// is what buys the range-for loop below -- an input iterator is the price.
class Items {
    int page_ = 0, index_ = 0;
    const std::array<std::string_view, 4>* batch_ = nullptr;
    bool done_ = false;
    std::string_view current_;

    bool advance() {
        for (;;) {
            if (batch_ && index_ < static_cast<int>(batch_->size())) {
                current_ = (*batch_)[index_++];
                return true;
            }
            if (done_) return false;
            bool has_more = false;
            batch_ = &fetch_page(++page_, has_more);
            index_ = 0;
            done_ = !has_more;
        }
    }

public:
    class iterator {
        Items* owner_;
    public:
        explicit iterator(Items* o) : owner_(o) {}
        std::string_view operator*() const { return owner_->current_; }
        iterator& operator++() { if (!owner_->advance()) owner_ = nullptr; return *this; }
        bool operator!=(const iterator& other) const { return owner_ != other.owner_; }
    };

    iterator begin() { return advance() ? iterator(this) : iterator(nullptr); }
    iterator end() { return iterator(nullptr); }
};

int main() {
    int taken = 0;
    Items items;
    for (std::string_view item : items) {
        std::cout << item << "\n";
        if (++taken == 6) break;
    }
    std::cout << "--- took " << taken << " items, fetched 2 of " << PAGES.size() << " pages\n";
}

Nothing is provided, so everything is visible. The state is a struct you pass in, and "no more items" has to be encoded in the return value as NULL -- there is no option type to say it for you. This is what every version above is doing underneath.

/* Lazy pagination: walk every item across pages, fetching a page only when
   the consumer actually needs an item from it. */
#include <stdio.h>
#include <stddef.h>

#define PAGE_COUNT 3
#define PAGE_SIZE  4

static const char *PAGES[PAGE_COUNT][PAGE_SIZE] = {
    {"alpha", "beta", "gamma", "delta"},
    {"epsilon", "zeta", "eta", "theta"},
    {"iota", "kappa", "lambda", "mu"},
};

/* Stands in for an API call. Prints so laziness is visible, not claimed. */
static const char **fetch_page(int n, int *has_more) {
    printf("fetch page %d\n", n);
    *has_more = n < PAGE_COUNT;
    return PAGES[n - 1];
}

/* C has no iterators and no yield, so the state is a plain struct you carry
   yourself, and "next" is just a function that reads and updates it. */
typedef struct {
    int page;
    const char **batch;
    int index;
    int count;
    int done;
} Items;

static void items_init(Items *it) {
    it->page = 0; it->batch = NULL; it->index = 0; it->count = 0; it->done = 0;
}

/* Returns NULL when the sequence is exhausted -- the absence of a value has
   to be encoded in the return type, because there is no Option or null-safety. */
static const char *items_next(Items *it) {
    for (;;) {
        if (it->index < it->count) return it->batch[it->index++];
        if (it->done) return NULL;
        int has_more = 0;
        it->batch = fetch_page(++it->page, &has_more);
        it->index = 0;
        it->count = PAGE_SIZE;
        it->done = !has_more;
    }
}

int main(void) {
    Items it;
    const char *item;
    int taken = 0;
    items_init(&it);
    while (taken < 6 && (item = items_next(&it)) != NULL) {
        printf("%s\n", item);
        taken++;
    }
    printf("--- took %d items, fetched 2 of %d pages\n", taken, PAGE_COUNT);
    return 0;
}

Conforming to Sequence and IteratorProtocol at once is the common shorthand: a type that is its own iterator gets makeIterator() for free. mutating is required and compiler-enforced, which makes the state change explicit in the signature.

// Lazy pagination: walk every item across pages, fetching a page only when
// the consumer actually needs an item from it.
let PAGES = [
    ["alpha", "beta", "gamma", "delta"],
    ["epsilon", "zeta", "eta", "theta"],
    ["iota", "kappa", "lambda", "mu"],
]

/// Stands in for an API call. Prints so laziness is visible, not claimed.
func fetchPage(_ n: Int) -> ([String], Bool) {
    print("fetch page \(n)")
    return (PAGES[n - 1], n < PAGES.count)
}

/// Conforming to both protocols at once is the common shorthand: Sequence
/// supplies makeIterator() for free when the type is its own iterator.
struct Items: Sequence, IteratorProtocol {
    private var page = 0
    private var batch: [String] = []
    private var index = 0
    private var done = false

    /// `mutating` because a struct's state changes; the compiler enforces it.
    mutating func next() -> String? {
        while true {
            if index < batch.count {
                defer { index += 1 }
                return batch[index]
            }
            if done { return nil }
            page += 1
            let (newBatch, hasMore) = fetchPage(page)
            batch = newBatch
            index = 0
            done = !hasMore
        }
    }
}

var taken = 0
// prefix(6) is lazy -- it pulls six values and no more.
for item in Items().prefix(6) {
    print(item)
    taken += 1
}
print("--- took \(taken) items, fetched 2 of \(PAGES.count) pages")