如何用递归方案（Catamorphism/Anamorphism）实现格路径算法？

1. 定义递归结构的Functor #

首先需要定义一个描述格路径递归逻辑的Functor，覆盖所有可能的分支：

data LatticeF a
  = BaseCase          -- 对应(0,0)的终止状态，结果为1
  | InvalidCase       -- 对应m<0或n<0的无效状态，结果为0
  | RecCase a a       -- 对应递归分支，分解为两个子问题
  deriving (Functor, Show, Eq)

2. 实现Coalgebra（构建递归树） #

Coalgebra负责将输入的(m,n)转换为LatticeF结构，完成递归树的展开（即构建调用栈）：

latticeCoalgebra :: (Int, Int) -> LatticeF (Int, Int)
latticeCoalgebra (m, n)
  | m == 0 && n == 0 = BaseCase
  | m < 0 || n < 0   = InvalidCase
  | otherwise        = RecCase (m - 1, n) (m, n - 1)

这个函数会递归分解每个有效状态，直到触达终止或无效状态，生成完整的调用结构。

3. 实现Algebra（归约求值） #

Algebra负责对展开后的递归结构进行求值，对应普通递归的计算逻辑：

latticeAlgebra :: LatticeF Int -> Int
latticeAlgebra BaseCase     = 1
latticeAlgebra InvalidCase  = 0
latticeAlgebra (RecCase x y) = x + y

4. 组合为Hylomorphism #

Hylomorphism是Anamorphism与Catamorphism的组合，直接复用你定义的cata和ana即可。可以封装一个通用的hylo函数：

hylo :: Functor f => Algebra f a -> Coalgebra f b -> b -> a
hylo alg coalg = cata alg . ana coalg

-- 最终的格路径计数函数
latticePaths :: Int -> Int -> Int
latticePaths m n = hylo latticeAlgebra latticeCoalgebra (m, n)

验证结果 #

调用latticePaths 2 3会返回10，与示例输出一致。

核心逻辑说明 #

• ana latticeCoalgebra负责构建调用栈/递归树：从输入(m,n)出发，不断分解为子问题，直到所有叶子节点都是终止或无效状态。
• cata latticeAlgebra负责从底向上求值：从叶子节点的结果开始，合并每个分支的计算结果，最终得到根节点的总路径数。
• 这种拆分方式将递归的“结构生成”和“计算逻辑”完全分离，是递归方案的核心优势。

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