skip to content

How would you generate a Fibonacci sequence with generateSequence, and what does this reveal about carrying state in the seeded overload?

level: middleimportance: should knowfreq 35%

answer

  1. Element carries state: use a Pair
  2. Seed = 0 to 1
  3. (a, b) -> b to (a + b)
  4. map { it.first } to project
  5. Long/BigInteger to avoid Int overflow

basics

~20 s

Because each Fibonacci number needs the two before it, you make the element a pair (a, b). The seed is the first pair, and next turns (a, b) into (b, a+b). Then map each pair to its first number.

solid answer

~40 s

The seeded overload only hands you the previous element, so to remember more than one prior value you make the element itself carry the needed state — here a Pair. generateSequence(Pair(0, 1)) { (a, b) -> Pair(b, a + b) } produces (0,1),(1,1),(1,2),(2,3)... and you map { it.first } to get 0,1,1,2,3,5,... Take what you need: .take(10).toList(). This shows the core idiom: when next requires history, encode that history in the element type (a Pair, a data class, or a small holder), keep nextFunction pure, and don't reach for external mutable variables. Use Long or BigInteger to avoid Int overflow for larger indices. Compared to mutating outside vars, this stays referentially clean and is safely re-iterable.

code

kotlin · 3 lines
kotlin
val fibs = generateSequence(0L to 1L) { (a, b) -> b to (a + b) }
    .map { it.first }
println(fibs.take(10).toList()) // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

go deeper

for a junior

Can follow that a Pair holds the two needed values and that the seed is the first pair.

for a middle

Writes the Pair-based generator independently and projects with map; knows the destructuring syntax.

for a senior

Explains purity vs captured-var single-pass trade-offs and re-iterability implications.

for a principal

Generalizes the lift-state-into-element pattern to arbitrary recurrences and reasons about numeric type/overflow choices in production.

## The constraint The seeded overload's `nextFunction` signature is `(T) -> T?` — it receives **only the previous element**. Fibonacci needs the **two** preceding numbers, so a single `Int` element isn't enough state. The idiom: **make the element type carry all the state you need**. ## Pair-based solution ```kotlin val fibs: Sequence<Int> = generateSequence(0 to 1) { (a, b) -> b to (a + b) } .map { it.first } fibs.take(10).toList() // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] ``` - `0 to 1` is the **seed** `Pair(0, 1)` — `a = 0`, `b = 1`. - `(a, b) -> b to (a + b)` **destructures** the previous pair and produces the next pair. State "rolls forward". - `.map { it.first }` projects each pair down to the visible Fibonacci value. ## Why not mutable vars? You *could* write a seedless version closing over two `var`s, but that makes the sequence **impure and single-pass**: re-iterating gives different results because the captured `var`s have advanced. The Pair approach keeps `nextFunction` **pure**, so the sequence is **referentially transparent** and **re-iterable** — `fibs.take(5)` and later `fibs.take(8)` both start from 0. ## Generalizing For richer state use a `data class` instead of `Pair` for readability: ```kotlin data class Step(val prev: Long, val curr: Long) val fibs = generateSequence(Step(0, 1)) { Step(it.curr, it.prev + it.curr) } .map { it.prev } ``` ## Overflow `Int` overflows around Fibonacci index 47. Use **`Long`** for moderate ranges or **`java.math.BigInteger`** for arbitrary precision: ```kotlin generateSequence(BigInteger.ZERO to BigInteger.ONE) { (a, b) -> b to (a + b) } ``` ## Key takeaway Whenever the next value depends on **more than one** prior value (or accumulated context), **lift that context into the element type** and keep the generator a pure function of it. This is the seeded overload's standard pattern for stateful recurrences.

  • Why prefer a Pair/data class over capturing two mutable vars?
    It keeps nextFunction pure, so the sequence is re-iterable and gives the same result each time, whereas captured vars advance and make it single-pass.
  • How do you avoid Int overflow for large Fibonacci indices?
    Use Long for moderate ranges or BigInteger for arbitrary precision; the same Pair pattern applies with those types.

Like passing a relay baton that holds two notes: each runner reads both, writes the new total, and hands forward the updated baton.

saying these in an interview costs you the question

  • Trying to use a single Int element and getting stuck on needing two prior values
  • Capturing mutable vars and claiming the sequence is still pure/re-iterable
  • Forgetting to map the Pair down to the value
  • Ignoring Int overflow
  • Swapping the pair update order (producing wrong successors)

context

resolving links…