haskell - 原始递归和 catamorphisms 之间有什么联系？

对自然数使用以下 catamorphism 我可以实现各种算术算法而不必处理递归:

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 的哪种组合，至少它的每个应用程序似乎都可以终止。在每次迭代中，整个问题都被最小/最简单的问题实例分解。因此，即使它在技术上不是原始递归，它似乎也具有同样的表现力。如果这是真的，则意味着 catamorphism 不足以表达一般递归。为此，我们可能需要一个hylomorphism。我的推理是否正确，也就是说，等价性是否适用于任何类型的 catamorphism，而不仅仅是自然数？

最佳答案

原始递归直接对应于一个paramorphism。
您是正确的，即 catamorphism 具有与 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(现实世界，不是这个例子)的大多数用途都不会产生函数，也不想访问列表的未处理尾部。对他们来说，仅仅因为传递较少的数据，catamorphism 的效率会稍微提高一些。
因此，就理论功率而言，它们是等效的。在操作方面，每个都有用，尽管 catamorphisms 更常见。
对于这个想法的一些更一般的扩展，请参阅 recursion-schemes 库。它使用了一个相当不同的想法公式，以便它可以抽象具有不同形状的数据类型，而不是需要为它们可以应用的每种数据类型的 cata/para 使用不同的类型。但它实际上只是包装相同想法的另一种方式，并且还涵盖了其他类型的态射，包括许多 more niche(甚至 possibly useless )。

关于haskell - 原始递归和 catamorphisms 之间有什么联系？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/62491307/