Baccata's recursion schemes microlib (to copy/paste when needed). Only depends on cats-core.

recursion.scala

import cats._
import cats.syntax.all._

// format: off
/**
  * A couple recursion-schemes, named in a less arcanic fashion than usual.
  * These functions allow to decouple the recursive aspect of model construction
  * and validation, from the domain-specific concerns.
  */
object recursion {

  type Fold[Pattern[_], A] = Pattern[A] => A
  type FoldF[F[_], Pattern[_], A] = Pattern[A] => F[A]

  type Unfold[Pattern[_], A] = A => Pattern[A]
  type UnfoldF[F[_], Pattern[_], A] = A => F[Pattern[A]]

  /**
   * Traditionally called "hylo" for hylomorphism
   * (hylo == matter, morphism == change)
   *
   * The only recursive function in here. All other recursions/corecursions
   * originate from this function.
   *
   * Essentially, this takes a value A, expands it into a Pattern tree, and collapses
   * that tree into a value B, in a way that never requires the full tree to be in
   * memory.
   *
   * @param a the seed value
   * @param f the [[Fold]] function that collapses only one layer of pattern tree at a time
   * @param u the [[Unfold]] function that expands only one layer of a pattern tree at a time
   * @tparam Pattern the pattern functor (typically mirroring single layers of tree-like structure)
   * @tparam A the type of the original seed value
   * @tparam B the target type of the refold
   */
  def refold[Pattern[_]: Functor, A, B](
      unfold: Unfold[Pattern, A],
      fold: Fold[Pattern, B]
    )(a: A): B =
    fold(unfold(a).map(refold(unfold, fold)))

  /**
   * A monadic version of [[refold]] that can process separate branches in a
   * non-sequential way, typically used when the unfold has to be validated
   * and the accumulation of errors is desirable.
   */
  def refoldPar[F[_]: Parallel, Pattern[_]: Traverse, A, B](
      unfold: UnfoldF[F, Pattern, A],
      fold: FoldF[F, Pattern, B]
    )(a: A): F[B] = {

    type FP[T] = F[Pattern[T]] // composition of F and Pattern
    implicit val F: Monad[F] = Parallel[F].monad
    implicit val FP: Functor[FP] = Functor[F].compose[Pattern]

    def fold2(fpfb: F[Pattern[F[B]]]): F[B] = for {
      fmb <- fpfb
      fb <- fmb.parSequence
      f <- fold(fb)
    } yield f

    refold[FP, A, F[B]](unfold, fold2)(a)
  }

}