skip to content

A retry helper builds a never-ending sequence of back-off delays, then takes the first five - why does building it not run forever?

level: juniorimportance: must knowfreq 62%

answer

  1. a description, not a collection
  2. nothing is computed at definition
  3. a seed plus a next-element rule
  4. elements appear only on demand
  5. the prefix length decides the work

basics

~20 s

An unbounded sequence is a recipe, not a collection: a seed plus a rule for the next element, computed only when something demands it. Building it stores the rule; taking five runs the rule four times.

solid answer

~40 s

An endless sequence is a **producer**, not a container. What the program holds is a seed - the first delay - and a step rule that turns any element into the one after it. Writing that definition allocates the rule and nothing else; zero delays exist yet. A take-first-five step then pulls one element at a time: the seed is given, the rule runs four times, and the pull stops. Element six is never produced, because nothing asked for it. The sequence is "endless" only in the sense that the rule carries no stopping condition; how far it is ever driven is decided entirely at the consuming end. That is also why the same definition is safe to reuse - each consumer drives it as far as it needs and no further.

code

pseudocode · 11 lines
pseudocode
function next_delay(previous):
    return previous * 2

// a description: a seed, and how to get the element after any element
delays = sequence(seed = 100, step = next_delay)

// nothing has run yet - no delay exists except the seed

first_five = take(delays, 5)
// pulls five times: 100, 200, 400, 800, 1600
// next_delay ran four times; element six was never produced

go deeper

for a junior

Recall the one-line reason: an endless sequence is a rule for making the next element, so writing it down computes nothing, and the work stops once the prefix the caller asked for is filled.

for a middle

Explain the pull. The take step demands elements one at a time, each demand costs one application of the step rule, and the definition itself never contains a stopping condition.

for a senior

Be able to say which operations over such a producer are safe in a running service, and to spot the ones that quietly drive it toward exhaustion instead of toward a bounded prefix.

for a principal

Weigh whether an unbounded producer should cross a module boundary at all: callers gain the freedom to choose their own bound, and gain a way to hang a thread that a bounded return value would not have handed them.

## A description, not a collection An unbounded sequence is usually introduced as "a list of all the doubling delays", which is exactly the picture that makes it sound impossible. Nothing in a running program holds infinitely many values. What the program holds is a **producer**: a **seed** - the first element - and a **step rule** that maps any element to the one after it. The retry helper holds the number `100` and the rule "double the previous delay". That pair is small, fixed-size data. It would be exactly the same size if the rule stopped after three elements, because a stopping condition is not part of it. This is what people mean when they call a lazy sequence a **recipe**. A recipe that says "keep adding stock and simmering" is a few lines long no matter how long anybody simmers. Reading it costs nothing; cooking costs what you cook. ## Why the definition runs nothing Under **non-strict** (lazy) evaluation an element is computed when something **demands** it, and not before. Three consequences follow, and together they are what makes an endless definition safe to write: - **Construction is constant in time and space.** Building the producer stores a seed and a rule. No element after the seed exists. - **There is no length to compute.** A strict collection knows its size because it holds its elements; a producer knows only how to make one more. - **The producer never asks whether it should continue.** It has no terminating case and needs none - it is only ever asked for the next element, one at a time. ## Where the work actually happens The consuming end drives everything. A take-first-five step demands element one, then two, and stops the instant it has five. Traced against a seed of 100 and a doubling rule: | demand | what the rule does | elements so far | |---|---|---| | first element | nothing - the seed is given | 100 | | next element | 100 x 2 | 100, 200 | | next element | 200 x 2 | ..., 400 | | next element | 400 x 2 | ..., 800 | | next element | 800 x 2 | ..., 1600 | Five elements cost **four** applications of the rule, because the seed is given rather than computed. Then the pulling stops: the take step has what it asked for and demands nothing more, so element six is never produced and never existed. ## Who decides how far it goes The producer has no opinion about where the sequence ends; the **consumer** decides, by how much it pulls. That is a design property, not a technicality: 1. **One definition serves many policies.** One caller retries three times, another keeps going while the delay stays under five seconds, a third stops when a deadline passes. All three drive the same producer. 2. **The bound lives where the knowledge lives.** The code that knows the retry budget sets it, instead of a shared helper guessing a number on everyone's behalf. 3. **Reuse is interference-free** for a pure producer: each consumer drives the same rule from the same seed and sees the same elements, because the rule is a function of the previous element, not of a shared position that someone else can advance. ## The obligation it hands you Two things must hold for a bounded pull to finish, and a producer that breaks either one is not safe merely because it is lazy: - **Each element must be produced in finite time.** A step rule that loops, or that itself demands an unbounded number of elements, hangs on the very first demand. - **Something must bound the demand.** Laziness makes an endless definition harmless; it does nothing about a consumer that keeps asking. A step that has to reach the end of the sequence before it can answer will pull until the process dies. The first half is the screening answer - defining costs nothing. The half that catches people in production is the second: **cheap to define is not cheap to consume**. The same three lines that cost nothing to write will pin a core at full load the moment something downstream asks for a total, a maximum or a sorted copy of them.

  • What has to be true of the step rule for a take-first-n to terminate?
    Every application of it must finish in finite time, and it must not itself demand an unbounded number of elements from somewhere else. Laziness only defers work; it does not rescue a rule that loops on its first invocation. If one application hangs, the very first demand hangs, and the fact that the caller asked for only five elements changes nothing.
  • If two consumers each take a prefix of the same endless definition, do they interfere with each other?
    Not for a pure producer. The rule is a function of the previous element, so each consumer drives it from the same seed and sees the same elements; neither can consume the other's. A producer that carries a mutable cursor instead is a different animal - one consumer advances the position and the other picks up the tail, which is a stateful iterator rather than a lazy description.

A knitting pattern that says "repeat this row forever" is one page of instructions, not an endless scarf. You get exactly as much fabric as you knit, and the pattern costs the same whether you knit five rows or none.

saying these in an interview costs you the question

  • Thinks the runtime produces all the elements up front and just stops early.
  • Says an endless sequence needs a large but finite cap to be safe.
  • Believes the producer, not the consumer, decides how many elements exist.
  • Claims the definition costs memory proportional to the number of elements.
  • Confuses the definition being cheap with every consumer of it being cheap.