作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
使用以下自然数的变态,我可以实现各种算术算法,而无需处理递归:
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
提供。在每次迭代中,整个问题都被最小/最简单的问题实例分解。因此,即使它在技术上不是原始递归,它似乎也具有同样的表现力。如果这是真的,则意味着变态不足以表达一般递归。我们可能需要一个hylomorphism。我的推理是否正确,也就是说,是否对任何类型的变质都成立,而不仅仅是自然数?
最佳答案
原语递归直接对应于一个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
的大多数用途(现实世界,不是这个例子)不产生函数并且不想访问列表的未处理尾部。对他们来说,仅仅因为传递更少的数据,变质将稍微更有效率。
cata
的不同类型。/
para
对于可以应用的每种数据类型。但它实际上只是打包相同想法的另一种方式,并且还涵盖了其他类型的态射,包括许多
more
niche (甚至
possibly useless )的。
关于haskell - 原始递归和变态之间有什么联系?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62491307/
我是一名优秀的程序员,十分优秀!