skip to content

Folding collapses a list of appointment dates to one value; what does the mirror-image unfolding operation take and produce?

level: seniorimportance: nice to knowfreq 28%

answer

  1. reverse the arrow
  2. seed in, structure out
  3. step returns element plus next seed
  4. stop report replaces the empty case
  5. anamorphism against catamorphism

basics

~20 s

Unfolding takes a seed and a step and produces a structure. The step turns one seed into an element plus the next seed, or reports stop. Folding is a structure in and a value out; unfolding is that arrow reversed.

solid answer

~50 s

Reverse every arrow. A fold starts from an existing structure and a combining function and returns one value; an unfold starts from a **seed** and a **step** and returns a structure. The signatures mirror: the fold's `combine(element, accumulator)` takes two things and gives back one, while the unfold's `step(seed)` takes one thing and gives back two — an element and the next seed — or a stop marker. Where they end mirrors too: a fold ends because the input runs out, an unfold ends because its step says so. The classical names carry the same symmetry — a fold is a **catamorphism**, a collapsing; an unfold is an **anamorphism**, a building up. For a recurring appointment series, the unfold is the natural expression: the rule and the anchor are the seed, and the dates are what comes out.

code

pseudocode · 7 lines
pseudocode
// collapsing: a structure goes in, one value comes out
// combine(element, accumulator) -> accumulator
fold(structure, initial, combine)

// building: one seed goes in, a structure comes out
// step(seed) -> STOP, or pair(element, nextSeed)
unfold(seed, step)

go deeper

for a junior

Recall the pairing rather than the terminology: one operation turns a collection into a single value, the other turns a single starting value into a collection. Knowing which direction each goes is enough at this stage.

for a middle

Explain the mirrored signatures out loud: two arguments in and one out on the collapsing side, one argument in and two out on the building side, with a stop report standing where the empty case stood.

for a senior

Use the symmetry in design. Recognise a build-then-collapse pipeline inside a loop someone wrote by hand, and say which half is the producer, which is the collapse, and what testing each separately buys you.

for a principal

Judge when naming the pair is worth it. Expressing a series as a seed and a step buys storable positions and reusable halves; on a team unfamiliar with the vocabulary, that has a teaching cost you should weigh rather than assume away.

## The mirror, stated once Take a fold: it has an existing structure, a starting value and a way to combine an element with what has been accumulated so far, and it returns a single value. Now reverse every arrow in that description and you get an unfold: it has a seed, and a way to turn that seed into one element plus the seed for the rest, and it returns a structure. One direction takes a structure apart into a value; the other builds a structure out of a value. The traditional names say the same thing: a fold is a **catamorphism** (a collapsing) and an unfold is an **anamorphism** (a building up). The reason to learn the pair rather than the two operations separately is that each one explains the other's odd corners. Why does a fold need a starting value? Because it must say what an empty structure yields. Why does an unfold need a stop report? Because it must say when to stop producing. Those are the same question seen from two sides. ## The two signatures, side by side | | fold (catamorphism) | unfold (anamorphism) | |---|---|---| | starts from | a structure already built | a seed value | | its function | `combine(element, accumulator)` returns an accumulator | `step(seed)` returns stop, or an element and the next seed | | arity direction | two in, one out | one in, two out | | what ends it | the input structure running out | the step reporting no further element | | edge case it must state | what an empty structure yields | when to stop producing | | result | one value | a structure | | over `n` elements | a standard left-to-right fold applies `combine` `n` times | a run of `n` elements calls `step` `n` times, plus once more to learn it should stop | Counting matters in an interview: for `n` elements a straightforward fold performs `n` combining steps, and an unfold that produces `n` elements and then stops performs `n + 1` step calls, because the stop has to be discovered. Candidates who have only ever used these as library vocabulary usually cannot say that. ## Seed and accumulator are not the same thing The two roles rhyme, which is why they get confused, but they face in opposite directions: - An **accumulator** summarises the part already visited. It is meaningful only alongside the rest of the structure still to be walked, and it is thrown away except for its final value. - A **seed** describes the part still to be produced. It is meaningful on its own — it names a position in the series — and each one is handed on to the next step. That difference is why a seed can be stored and resumed while an accumulator generally cannot be interpreted without the structure it was walking. ## The appointment series as an unfold A recurring appointment is a natural anamorphism, and writing it as one makes the parts explicit: 1. The **seed** is the anchor date, the interval, the position reached, and — if the rule is bounded — how many occurrences remain. 2. The **step** computes the date for the current position and returns it with a seed advanced by one position, or reports stop when the remaining count reaches zero. 3. The **result** is the series, built outward. It is unbounded if the rule is unbounded, and the definition is none the worse for it. The mirror is worth noticing in practice: a report that says *how many appointments fall in this quarter* is an unfold immediately followed by a collapse. Building up and then tearing down is the general shape of what an imperative loop does in one piece, split into two named halves you can test and reuse separately. ## Where the symmetry is imperfect Stating the mirror is useful; claiming it is exact is an overstatement worth avoiding: - A fold over a finite structure is guaranteed to finish, because the structure bounds it. An unfold has no such external bound, so its argument for well-definedness is a different one. - A fold can be given several directions of association over the same structure; an unfold produces in one direction, from the seed outward. - A fold is usually presented as walking every element exactly once; an unfold's step decides for itself how many elements there will be. The honest summary: the shapes are mirror images, the guarantees are not.

  • Where does a fold's empty case appear in an unfold?
    In the step's stop report. A fold has to say what an empty structure yields; an unfold has to say when to stop producing. They are the same edge of the mirror seen from two sides: one names the end of the input, the other decides the end of the output.
  • Is the accumulator of a fold the same thing as a seed?
    No, they face opposite ways. An accumulator summarises the elements already visited and is discarded apart from its final value; a seed describes everything still to be produced and is handed on to the next step. That is why a seed names a position you can store and resume, while an accumulator only makes sense alongside the structure still being walked.
  • Is the symmetry between the two operations exact?
    The shapes mirror; the guarantees do not. A fold over a finite structure is bounded by that structure and finishes on its own, whereas an unfold has no external bound and needs a different argument for being well defined. A fold also admits more than one association order, while an unfold produces outward from the seed in one direction.

saying these in an interview costs you the question

  • Says an unfold is just a fold run in the other direction
  • Thinks an unfold needs an existing collection to walk
  • Describes the unfold's step as combining two values
  • Assumes an unfold must produce an unbounded structure
  • Confuses a fold's accumulator with an unfold's seed