corecursively

Corecursively is used to describe a definition or construction that is produced by corecursion, the dual concept to recursion. In corecursive definitions, outputs are generated progressively from a potentially infinite data structure rather than computed entirely from a finite input by reducing it. The term emphasizes the ongoing, producer-like nature of the definition.

Corecursion enables building infinite data structures, such as streams, by repeatedly applying a step that yields the next element and a continuation for the rest of the structure. A corecursive definition specifies how to generate the next portion of the output and how to proceed, rather than how to reduce a problem to simpler subproblems. This approach often relies on lazy evaluation or guarded recursion to ensure productivity, so that every finite portion can be produced in finite time.

From a formal perspective, corecursion is modeled in functional programming and category theory by unfold operations and anamorphisms, and by final coalgebras. A corecursive specification describes how to unfold a structure step by step, producing each new element while preserving an ongoing, coinductive process.

Common examples include infinite streams of natural numbers defined corecursively, where each step yields the next number and a reference to the remainder. Languages with lazy evaluation, such as Haskell, frequently express corecursive constructions for streams and other coinductive data. In proof systems, corecursion is paired with coinduction to reason about the correctness and productivity of such definitions.

Caveats exist: non-productive or poorly guarded corecursive definitions can lead to non-terminating or meaningless results. Some languages provide productivity checks or guarded corecursion constraints to mitigate these issues.

See also recursion, coinduction, anamorphism, coalgebra, streams.