原始递归和变形之间有什么联系？
What is the connection between primitive recursion and catamorphisms?
对自然数使用以下变质，我可以实现各种算术算法而无需处理递归：
cataNat :: b -> (b -> b) -> Natural -> b
cataNat zero succ = go
where
go n = if (n <= 0) then zero else succ (go (n - 1))
fib :: Natural -> Natural
fib = fst . cataNat (0, 1) (\(a, b) -> (b, a + b))
cataNat 在我看来类似于原始递归。至少它的每个应用程序似乎都保证终止，无论提供 zero 和 succ 的哪种组合。在每次迭代中，整个问题都被 smallest/simplest 问题实例分解。因此，即使它在技术上不是原始递归，它似乎也具有同样的表现力。如果这是真的，那就意味着同构不足以表达一般的递归。为此，我们可能需要一个同态。我的推理是否正确，也就是说，等价性是否适用于任何类型的变形，而不仅仅是自然数？
原始递归直接对应一个paramorphism
你是对的，变质具有与同态等效的理论能力，但它们在操作方面的重要方面可能不同。例如，让我们转到列表而不是 Nats。
cata :: b -> (a -> b -> b) -> [a] -> b
cata = flip foldr -- I'm lazy, but this argument order makes a bit more sense for this example
para :: b -> (a -> [a] -> b -> b) -> [a] -> b
para z _ [] = z
para z f (x:xs) = f x xs (para z f xs)
-- Removes the first element from the list which is equal to the other argument
delete1 :: Eq a => a -> [a] -> [a]
delete1 x xs = cata (const []) (\el k found -> if not found && el == x then k True else el : k found) xs False
-- Removes the first element from the list which is equal to the other argument
delete2 :: Eq a => a -> [a] -> [a]
delete2 x xs = para [] (\el raw processed -> if el == x then raw else el : processed) xs
看看 delete1 与 delete2 相比有多尴尬。您不仅需要通过使 cata 的结果成为一个函数来扭曲您的逻辑，而且还有非常实际的操作成本。你必须在找到匹配元素后遍历列表中的所有内容，并重新创建所有 (:) 构造函数。这可能会显着降低效率。相比之下，delete2，当它找到目标元素时，可以只使用列表的现有尾部作为余数，甚至不需要查看它。当然，大多数 foldr 的使用（现实世界，不是这个例子）不会产生函数并且不想访问列表的未处理尾部。对于他们来说，仅仅因为传递的数据更少，变质会稍微更有效率。
因此，就理论功率而言，它们是等效的。在操作方面，每个都有用处，尽管变形更常见。
要以更一般的方式对这个想法进行一些扩展，请参阅 recursion-schemes library. It uses a rather different-looking formulation of the idea so that it can abstract over data types with different shapes, instead of needing a different type for cata/para for each data type they can be applied to. But it really is just an alternate way of packing up the same ideas, and other kinds of morphisms are covered as well, including much more niche (or even possibly useless)。
对自然数使用以下变质，我可以实现各种算术算法而无需处理递归：
cataNat :: b -> (b -> b) -> Natural -> b
cataNat zero succ = go
where
go n = if (n <= 0) then zero else succ (go (n - 1))
fib :: Natural -> Natural
fib = fst . cataNat (0, 1) (\(a, b) -> (b, a + b))
cataNat 在我看来类似于原始递归。至少它的每个应用程序似乎都保证终止，无论提供 zero 和 succ 的哪种组合。在每次迭代中，整个问题都被 smallest/simplest 问题实例分解。因此，即使它在技术上不是原始递归，它似乎也具有同样的表现力。如果这是真的，那就意味着同构不足以表达一般的递归。为此，我们可能需要一个同态。我的推理是否正确，也就是说，等价性是否适用于任何类型的变形，而不仅仅是自然数？
原始递归直接对应一个paramorphism
你是对的，变质具有与同态等效的理论能力，但它们在操作方面的重要方面可能不同。例如，让我们转到列表而不是 Nats。
cata :: b -> (a -> b -> b) -> [a] -> b
cata = flip foldr -- I'm lazy, but this argument order makes a bit more sense for this example
para :: b -> (a -> [a] -> b -> b) -> [a] -> b
para z _ [] = z
para z f (x:xs) = f x xs (para z f xs)
-- Removes the first element from the list which is equal to the other argument
delete1 :: Eq a => a -> [a] -> [a]
delete1 x xs = cata (const []) (\el k found -> if not found && el == x then k True else el : k found) xs False
-- Removes the first element from the list which is equal to the other argument
delete2 :: Eq a => a -> [a] -> [a]
delete2 x xs = para [] (\el raw processed -> if el == x then raw else el : processed) xs
看看 delete1 与 delete2 相比有多尴尬。您不仅需要通过使 cata 的结果成为一个函数来扭曲您的逻辑，而且还有非常实际的操作成本。你必须在找到匹配元素后遍历列表中的所有内容，并重新创建所有 (:) 构造函数。这可能会显着降低效率。相比之下，delete2，当它找到目标元素时，可以只使用列表的现有尾部作为余数，甚至不需要查看它。当然，大多数 foldr 的使用（现实世界，不是这个例子）不会产生函数并且不想访问列表的未处理尾部。对于他们来说，仅仅因为传递的数据更少，变质会稍微更有效率。
因此，就理论功率而言，它们是等效的。在操作方面，每个都有用处，尽管变形更常见。
要以更一般的方式对这个想法进行一些扩展，请参阅 recursion-schemes library. It uses a rather different-looking formulation of the idea so that it can abstract over data types with different shapes, instead of needing a different type for cata/para for each data type they can be applied to. But it really is just an alternate way of packing up the same ideas, and other kinds of morphisms are covered as well, including much more niche (or even possibly useless)。