基于递归格式的点阵路径算法

Question

我正在讨论一些递归方案，即变质和变形，并想尝试实现格点路径算法的解决方案，如下所述(摘自一系列采访问题)：

Prompt:  Count the number of unique paths to travel from the top left
          order to the bottom right corner of a lattice of M x N squares.

          When moving through the lattice, one can only travel to the
          adjacent corner on the right or down.

 Input:   m {Integer} - rows of squares
 Input:   n {Integer} - column of squares
 Output:  {Integer}

 Example: input: (2, 3)

          (2 x 3 lattice of squares)
           __ __ __
          |__|__|__|
          |__|__|__|

          output: 10 (number of unique paths from top left corner to bottom right)**

使用正常的递归，您可以使用如下的方法来解决这个问题：

lattice_paths m n =
         if m == 0 and n == 0 then 1
         else if m < 0 or n < 0 then 0
         else (lattice_paths (m - 1) n) + lattice_paths m (n - 1)

我的Fix、cata和ana的定义如下：

newtype Fix f = In (f (Fix f))

deriving instance (Eq (f (Fix f))) => Eq (Fix f)
deriving instance (Ord (f (Fix f))) => Ord (Fix f)
deriving instance (Show (f (Fix f))) => Show (Fix f)

out :: Fix f -> f (Fix f)
out (In f) = f

-- Catamorphism
type Algebra f a = f a -> a

cata :: (Functor f) => Algebra f a -> Fix f -> a
cata f = f . fmap (cata f) . out

-- Anamorphism
type Coalgebra f a = a -> f a

ana :: (Functor f) => Coalgebra f a -> a -> Fix f
ana f = In . fmap (ana f) . f

本文(https://stackoverflow.com/a/56012344)中提到的编写从Int -> Int开始的递归方案的方法是编写一个同胚，其中非变态类构建调用堆栈，而变形则构建所述调用堆栈的计算。我不知道怎么在这里建立调用堆栈。

Answer 1

也许是这样的：

data CallStack a = Plus a a | Base Int deriving Functor

produceStack :: Coalgebra CallStack (Int, Int)
produceStack (m, n) =
    if m == 0 && n == 0 then Base 1
    else if m < 0 || n < 0 then Base 0
    else Plus (m-1, n) (m, n-1)

consumeStack :: Algebra CallStack Int
consumeStack (Base n) = n
consumeStack (Plus a b) = a + b

"Stack“是这个调用结构的一个有趣的名称。不是很像堆叠。