Scala中Chronomorphisms：futu与dynamo的示例及原理问询

一、Futumorphism 实用 Scala 示例 #

Futumorphism（futu）是支持动态递归构造的模式，它的 coalgebra 返回 Free[F,X]，可以灵活控制递归的终止或分支，适合处理需要按需展开、动态决定递归深度的场景。

示例：深度受限二叉树构造 #

我们用 futu 构造一个可指定最大深度的二叉树，通过 Free 控制递归的终止：

import cats.Functor
import cats.free.Free
import cats.free.Free.{Pure, Roll}
import cats.free.Fix

// 定义二叉树的 Functor
sealed trait TreeF[A]
case class LeafF[A]() extends TreeF[A]
case class NodeF[A](left: A, right: A) extends TreeF[A]

object TreeF {
  implicit val functor: Functor[TreeF] = new Functor[TreeF] {
    override def map[A, B](fa: TreeF[A])(f: A => B): TreeF[B] = fa match {
      case LeafF() => LeafF()
      case NodeF(l, r) => NodeF(f(l), f(r))
    }
  }
}

// 定义 Futu 的 Coalgebra：根据当前深度决定递归行为
def depthLimitedCoalg(maxDepth: Int): Int => Free[TreeF, Int] = {
  // 深度为0时返回 Pure，终止递归
  case 0 => Pure(0)
  // 深度>0时返回 Roll，构造当前节点并继续递归子节点
  case currentDepth => Roll(NodeF(currentDepth - 1, currentDepth - 1))
}

// 调用 futu 生成完整的二叉树结构
val tree: Fix[TreeF] = futu(depthLimitedCoalg(3))

// 展开验证结构
def unfold(tree: Fix[TreeF]): TreeF[Fix[TreeF]] = tree.unfix
unfold(tree) 
// 输出：NodeF(Fix(NodeF(Fix(NodeF(Fix(LeafF()), Fix(LeafF()))), Fix(NodeF(Fix(LeafF()), Fix(LeafF())))), Fix(NodeF(Fix(NodeF(Fix(LeafF()), Fix(LeafF()))), Fix(NodeF(Fix(LeafF()), Fix(LeafF())))))

「未来」的指代

Free[TreeF, Int] 中的内容就是递归的「未来」：

• Pure(0) 表示未来不再生成子节点，递归终止；
• Roll(NodeF(...)) 表示未来需要继续递归构造左右子树，动态延续递归流程。

二、Dynamo 用于动态规划的 Scala 示例 #

Dynamo 是 ana（递归构造）和 histo（带记忆的递归折叠）的组合，完美适配动态规划场景：ana 构造问题的递归结构，histo 利用缓存的子问题结果（记忆化）计算最终值，避免重复计算。

示例：爬楼梯问题动态规划 #

问题：每次可爬1或2阶，求到达第n阶的方法数。

import cats.Functor
import cats.free.Cofree
import cats.free.Fix

// 定义爬楼梯问题的 Functor，描述子问题结构
sealed trait ClimbF[A]
case class BaseClimb[A]() extends ClimbF[A] // 基准情况：0阶
case class OneStep[A](prev: A) extends ClimbF[A] // 1阶，子问题为0阶
case class TwoSteps[A](prev1: A, prev2: A) extends ClimbF[A] // n阶，子问题为n-1和n-2阶

object ClimbF {
  implicit val functor: Functor[ClimbF] = new Functor[ClimbF] {
    override def map[A, B](fa: ClimbF[A])(f: A => B): ClimbF[B] = fa match {
      case BaseClimb() => BaseClimb()
      case OneStep(p) => OneStep(f(p))
      case TwoSteps(p1, p2) => TwoSteps(f(p1), f(p2))
    }
  }
}

// 1. Ana 的 Coalgebra：构造爬楼梯的递归问题结构
def climbCoalg(n: Int): ClimbF[Int] = n match {
  case 0 => BaseClimb()
  case 1 => OneStep(0)
  case k => TwoSteps(k - 1, k - 2)
}

// 2. Histo 的 Algebra：利用 Cofree 缓存的子问题结果计算当前值
def climbAlg(cofree: Cofree[ClimbF, Int]): Int = cofree.head match {
  case BaseClimb() => 1 // 0阶有1种方法（原地不动）
  case OneStep(_) => cofree.tail.head // 1阶的方法数等于0阶的结果
  case TwoSteps(_, _) => cofree.tail.head + cofree.tail.tail.head // n阶方法数 = n-1阶 + n-2阶的结果
}

// 用 Dynamo 组合构造与计算，得到最终求解函数
val climbStairs: Int => Int = dynamo(climbCoalg, climbAlg)

// 测试
climbStairs(5) // 输出8，正确对应5阶的8种爬法

「过去」与「未来」的指代

• 「未来」（Ana 阶段）：climbCoalg 根据当前阶数生成的 ClimbF[Int] 描述了「未来需要求解的子问题」，比如对于5阶，未来需要求解4阶和3阶的子问题，ana 会递归构造完整的问题结构。
• 「过去」（Histo 阶段）：Cofree[ClimbF, Int] 中包含的子节点计算结果就是「过去已经求解完成的子问题答案」，histo 直接复用这些缓存值，避免了重复计算，这正是动态规划的核心记忆化逻辑。

内容的提问来源于stack exchange，提问作者Sergey Sviridov