Monadic recursion sequences recursive computations through an effect type instead of calling the recursive function directly. In streaming code, this lets Pull interpret outputs, results, effects, and continuation steps while preserving composability. section 15.3 section 15.6
The pattern appears when a recursive interpreter must:
- Represent each step as F[Either[R, (O, Pull[F, O, R])]], separating completion from another output and continuation. section 15.3
- Use flatMap to sequence the next recursive step inside the Monad[F] constraint. section 15.3
- Rely on the effect monad’s stack-safe flatMap rather than tailrec for recursive fold and traversal operations. section 15.3
- Preserve compositional behavior for effects, early termination, resource safety, and incremental output. section 15.6
Interpreting a Pull
A step interpreter handles Result by returning F.unit(Left(r)), Output by returning the next value and continuation, Eval by mapping its action, and FlatMap by recursively sequencing through flatMap. Thus recursion describes both the remaining stream computation and the effects needed to execute it. section 15.3
def step[F2[x] >: F[x], O2 >: O, R2 >: R](
using F: Monad[F2] #1
): F2[Either[R2, (O2, Pull[F2, O2, R2])]] =
this match
case Result(r) => F.unit(Left(r)) #2
case Output(o) => F.unit(Right(o, Pull.done))
case Eval(action) => action.map(Left(_)) #3
case FlatMap(source, f) =>
source match
case FlatMap(s2, g) =>
s2.flatMap(x => g(x).flatMap(y => f(y))).step
case other => other.step.flatMap: #4
case Left(r) => f(r).step
case Right((hd, tl)) => F.unit(Right((hd, tl.flatMap(f))))
The complete step definition makes the transition from direct recursion to monadic recursion explicit, including Monad[F], flatMap, outputs, results, and effects. section 15.3
