Skip to content

lazy runs the chain one element at a time

Level: 201 · a Python programmer who thinks of map as a generator and wants to know why Ruby's returns an array

One line: map and select on an ordinary collection each run to the end and build an array before the next stage starts; lazy turns the same chain into an Enumerator::Lazy that pulls one element through every block only when a consumer such as first(n) asks — which is how an endless range can be mapped — and that is what Python's generators, map and filter do without being asked.

An eager chain is a sequence of whole arrays: (1..4).map { } produces four values, and only then does select look at them. A lazy chain is a pipeline: each adapter — map, select, take_while, each_slice, filter_map, with_index, zip, uniq, flat_map, drop_while, take — returns another Enumerator::Lazy that remembers what to do and does nothing, and a consumer — first(n), to_a (also spelled force), include?, sum, find, next — pulls elements through the whole pipeline one at a time and stops as soon as it has its answer. Two things follow: the blocks run interleaved, and the source may be endless. The trace lines under the two headings print the blocks in the order they ran.

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

Eager: every map runs, then every select
    map(1) map(2) map(3) map(4) select(10) select(20) select(30) select(40)
 1. (1..4).map { }.select { }                                [20, 30, 40]
Lazy: one element through both blocks, and it stops at the second hit
    map(1) select(10) map(2) select(20) map(3) select(30)
 2. (1..4).lazy.map { }.select { }.first(2)                  [20, 30]

An endless source, which only a lazy chain can map over
 3. (1..Float::INFINITY).lazy.map { }.select { }.first(3)    [6, 12, 18]
 4. (1..).lazy, same chain; map calls it took                [[6, 12, 18], 9]
 5. (1..).lazy.take_while { |x| x < 4 }.to_a                 [1, 2, 3]
 6. (1..).lazy.each_slice(2).first(2)                        [[1, 2], [3, 4]]
 7. (1..).lazy.filter_map { x * 2 if x.even? }.first(3)      [4, 8, 12]
 8. (1..).lazy.with_index.map { |x, i| x * i }.first(3)      [0, 2, 6]
 9. (1..).lazy.zip("a".."c").first(2)                        [[1, "a"], [2, "b"]]
10. (1..).lazy.map { |x| x % 3 }.uniq.first(3)               [1, 2, 0]
11. (1..).lazy.flat_map { |x| [x, -x] }.first(4)             [1, -1, 2, -2]
12. (1..).lazy.drop_while { |x| x < 5 }.first(2)             [5, 6]

Which calls stay lazy, and which ones run the chain
13. lazy.class, lazy.map { }.class                           [Enumerator::Lazy, Enumerator::Lazy]
14. lazy.take(2).class, lazy.first(2).class                  [Enumerator::Lazy, Array]
15. (1..).lazy.map { |x| x * x }.take(3).force               [1, 4, 9]
16. lazy.eager.class, lazy.eager.map { }.class               [Enumerator, Array]
17. (1..).lazy.include?(5), (1..3).lazy.map { x * 2 }.sum    [true, 12]
18. (1..).lazy.size, [1,2,3].lazy.map {}.size, .select {}.size [Infinity, 3, nil]
19. e = (1..).lazy.map { x * 2 }; e.next, e.next             [2, 4]
20. Enumerator::Lazy.ancestors.take(3)                       [Enumerator::Lazy, Enumerator, Enumerable]

Reading the output

The two traces are the lesson. Eager: map(1) map(2) map(3) map(4), then select(10) select(20) select(30) select(40) — every stage finishes before the next starts, and row 1 holds all three hits. Lazy: map(1) select(10) map(2) select(20) map(3) select(30) — each element goes through both blocks before the next element is touched, and because first(2) had its two hits after select(30), map(4) never ran. Same blocks, same answer for the first two, a different order and a different amount of work.

Rows 3–12 are the endless sources: (1..Float::INFINITY) and its shorter spelling, the endless range (1..). An eager map over either would never return; the lazy chain in row 3 finds the first three doubled numbers divisible by three, and row 4 counts what it cost — nine calls of the map block, because the hits are at 3, 6 and 9. Rows 5–12 are the adapters that keep a chain lazy: take_while, each_slice, filter_map, with_index, zip, uniq (which must remember what it has seen), flat_map, drop_while.

Rows 13–20 sort the methods into the two kinds. Every adapter returns another Enumerator::Lazy (row 13), and take(2) is an adapter where first(2) is a consumer that returns an Array (row 14) — so take(3) needs a force or to_a to produce anything (row 15). eager goes the other way: it wraps the lazy chain in an ordinary Enumerator, whose map builds an Array again (row 16). A consumer that can stop early still stops on an endless source (include?(5) in row 17), and sum on a finite one runs the chain to the end. Row 18 is size: (1..).lazy.size is Infinity, a lazy map keeps its source's size, and a lazy select reports nil because nobody can know how many elements will pass without running it. Row 19 is worth remembering: a Lazy is an Enumerator (row 20 shows the ancestry), so next pulls values from it one at a time — the external enumerators page — and the two ideas, laziness and external iteration, are one object.

Compared with Python

Python's chains are lazy unless you ask for a list. A generator expression (f(x) for x in xs) is Ruby's lazy.map, one with an if is lazy.select or lazy.filter_map, and the builtins map and filter return iterators too, so the trace under the second heading interleaves exactly as Ruby's did and stops after the second hit. The eager spelling is the list comprehension: the trace under the first heading, all maps then all selects, comes from two of them. itertools.islice(chain, n) is first(n) (but returns another iterator, so list(...) is the consumer), itertools.count(1) is (1..), batched is each_slice, takewhile and dropwhile are named the same, enumerate is with_index, zip pairs two sources, and chain.from_iterable is flat_map. Row 10 is the one adapter Python lacks: there is no lazy uniq in the standard library, so the twin writes a four-line generator with a seen-set.

Rows 13–20 read the other way round. There is no .lazy to call — generator, map and filter are the types of the lazy objects (row 13) — and no .eager either: list(...) or a comprehension is how a chain is run (rows 14–16). in stops early on count(1) just as include? did (row 17). len refuses an iterator with TypeError, and operator.length_hint is the polite question: it answers 3 for a list iterator and 0 for a map, which does not propagate its input's length (row 18) — Ruby's lazy map keeps the size and its select says nil. And row 19 is the same fact as in Ruby: the generator that is the lazy pipeline is also the object that next drives.

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

Eager: a list comprehension runs to its end before the next one starts
    map(1) map(2) map(3) map(4) select(10) select(20) select(30) select(40)
 1. [times_ten(x) for ...], then [x for ... if big(x)]       [20, 30, 40]
Lazy: generator expressions interleave, and islice stops at the second hit
    map(1) select(10) map(2) select(20) map(3) select(30)
 2. list(islice((x for x in (...) if big(x)), 2))            [20, 30]

An endless source: itertools.count, which only a lazy chain can map over
 3. islice((x for x in (x * 2 for x in count(1)) if % 3), 3) [6, 12, 18]
 4. filter(..., map(double, count(1))); map calls it took    [[6, 12, 18], 9]
 5. list(takewhile(lambda x: x < 4, count(1)))               [1, 2, 3]
 6. list(islice(batched(count(1), 2), 2))                    [(1, 2), (3, 4)]
 7. islice((x * 2 for x in count(1) if x % 2 == 0), 3)       [4, 8, 12]
 8. islice((x * i for i, x in enumerate(count(1))), 3)       [0, 2, 6]
 9. list(islice(zip(count(1), "abc"), 2))                    [(1, 'a'), (2, 'b')]
10. islice(unique(x % 3 for x in count(1)), 3)               [1, 2, 0]
11. islice(chain.from_iterable([x, -x] for x in count), 4)   [1, -1, 2, -2]
12. islice(dropwhile(lambda x: x < 5, count(1)), 2)          [5, 6]

Which objects are lazy, and which calls run the chain
13. type(genexp), type(map(...)), type(filter(...))          ['generator', 'map', 'filter']
14. type(islice(count(1), 2)), type(list(islice(...)))       ['islice', 'list']
15. list(islice((x * x for x in count(1)), 3))  (list = force) [1, 4, 9]
16. type([x for x in range(4)]), type(list(map(...)))        ['list', 'list']
17. 5 in count(1), sum(x * 2 for x in range(1, 4))           [True, 12]
18. len(count(1)) raises; length_hint(iter([1,2,3])), (map)  ['TypeError', 3, 0]
19. e = (x * 2 for x in count(1)); next(e), next(e)          [2, 4]
20. type(e).__mro__ names, isinstance(e, Iterator)           [['generator', 'object'], True]

Rust's iterators work the Ruby way with Python's defaults, and the sibling page Iterators are lazy ↗ draws the same adapter/consumer line with a trace of its own.

Try it

  1. Primes, lazily: (2..).lazy.select { |n| prime?(n) } with a trial-division prime? that also counts how many candidates it has tested. Print the first ten primes and the count, the first prime above 1000 and the count, the primes in slices of three, the first four twin-prime pairs (each_cons(2) plus select), the prime squares below 200 (map plus take_while), and the hundredth prime (with_index(1) plus find).
  2. Put an .eager in the middle of the traced chain — (1..4).lazy.map { }.eager.select { }.first(2) — and predict the trace before you run it. Then try (1..).lazy.map { }.eager.first(2): does it return?
Solution to 1

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

# Kata: primes, lazily. An endless range, one select, and consumers that stop.
def row(n, label, value) = puts(format("%2d. %-46s %s", n, label, value.inspect))

tested = 0
prime = ->(n) { tested += 1; (2..Integer.sqrt(n)).none? { |d| (n % d).zero? } }
primes = (2..).lazy.select(&prime)

row 1, "primes.first(10)", primes.first(10)
row 2, "candidates tested for those ten", tested
tested = 0
row 3, "primes.find { |p| p > 1000 }", primes.find { |p| p > 1000 }
row 4, "candidates tested for that one", tested
row 5, "primes.each_slice(3).first(2)", primes.each_slice(3).first(2)
row 6, "twin primes: each_cons(2).select { gap 2 }.first(4)", primes.each_cons(2).select { |a, b| b - a == 2 }.first(4)
row 7, "primes.map { p * p }.take_while { < 200 }.to_a", primes.map { |p| p * p }.take_while { |x| x < 200 }.to_a
row 8, "primes.with_index(1).find { |_, i| i == 100 }", primes.with_index(1).find { |_, i| i == 100 }

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

 1. primes.first(10)                               [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
 2. candidates tested for those ten                28
 3. primes.find { |p| p > 1000 }                   1009
 4. candidates tested for that one                 1008
 5. primes.each_slice(3).first(2)                  [[2, 3, 5], [7, 11, 13]]
 6. twin primes: each_cons(2).select { gap 2 }.first(4) [[3, 5], [5, 7], [11, 13], [17, 19]]
 7. primes.map { p * p }.take_while { < 200 }.to_a [4, 9, 25, 49, 121, 169]
 8. primes.with_index(1).find { |_, i| i == 100 }  [541, 100]

See also