我正在玩一些遞回方案，即 catamorphisms 和 anamorphisms，并想嘗試使用它們來實作如下所述的晶格路徑演算法的解決方案（取自面試問題的集合）：
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)
MyFix和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 開始的遞回方案的方法是撰寫一個hylomorphism，其中anamorphism 型別構建呼叫堆疊，catamorphism 評估所說的呼叫堆疊。我不確定如何在這里構建呼叫堆疊。
uj5u.com熱心網友回復：
也許是這樣的：
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
“堆疊”是這個呼叫結構的一個有趣的名字。它不是很像堆疊。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/532474.html
標籤：哈斯克尔递归方案