haskell - 如何使用自然数的折叠来定义斐波那契数列？

问题描述

我目前正在学习结构递归/变态意义上的折叠。我使用自然数的折叠来实现幂和阶乘。请注意，我几乎不知道 Haskell，所以代码可能很尴尬：

foldNat zero succ = go
  where
    go n = if (n <= 0) then zero else succ (go (n - 1))

pow n = foldNat 1 (n*)

fact n = foldNat 1 (n*) n

接下来我想调整斐波那契数列：

fib n = go n (0,1)
  where
    go !n (!a, !b) | n==0      = a
                   | otherwise = go (n-1) (b, a+b)

我有fib一对作为第二个参数，其字段在每次递归调用时交换。我被困在这一点上，因为我不了解转换过程的机制。

[编辑]

如评论中所述，我的fact功能是错误的。这是一个基于变形的新实现（希望如此）：

paraNat zero succ = go 
  where 
    go n = if (n <= 0) then zero else succ (go (n - 1), n)

fact = paraNat 1 (\(r, n) -> n * r)

标签： haskellrecursionfoldrecursion-schemescatamorphism

让类型指导您。这是您的foldNat，但带有类型签名：

import Numeric.Natural

foldNat :: b -> (b -> b) -> Natural -> b
foldNat zero succ = go
  where
    go n = if (n <= 0) then zero else succ (go (n - 1))

再看一下go你的实现中的帮助fib器，我们可以注意到递归案例接受并返回一(Natural, Natural)对。将其与后继论点进行比较foldNat表明我们想要b成为(Natural, Natural). 这是关于应该如何适应的一个很好的提示go：

fibAux = foldNat (0, 1) (\(a, b) -> (b, a + b))

（我暂时忽略了严格性的问题，但我会回到这一点。）

这还不完全fib是，通过查看结果类型可以看出。不过，正如 Robin Zigmond 指出的那样，解决这个问题是没有问题的：

fib :: Natural -> Natural
fib = fst . foldNat (0, 1) (\(a, b) -> (b, a + b))

此时，您可能想要向后工作并替换的定义foldNat来描绘这与显式递归解决方案的对应关系。

虽然这是一个非常好的实现fib，但它与您编写的那个之间有一个主要区别：这是一个惰性右折叠（Haskell catamorphisms 的规范），而您的显然是一个严格的左折叠. （是的，在这里使用严格的左折叠确实有意义：一般来说，如果您正在做的事情看起来像算术，那么您理想地需要严格的左折叠，而如果它看起来像构建数据结构，那么您需要懒惰的右折叠）。不过，好消息是我们可以使用变态来定义几乎所有递归消耗值的东西……包括严格的左折叠！在这里，我将使用 foldl-from-foldr 技巧的改编版本（有关列表情况下的详细解释，请参阅此问题），它依赖于如下函数：

lise :: (b -> b) -> ((b -> b) -> (b -> b))
lise suc = \g -> \n -> g (suc n)

这个想法是我们利用函数组合（\n -> g (suc n)与相同g . suc）以相反的顺序做事——就好像我们交换succ了. 可以用作的后继参数。这意味着我们最终会得到一个函数而不是 a ，但这不是问题，因为我们可以自己将它应用于零值。gogolise sucfoldNatb -> bb

由于我们想要一个严格的左弃牌，我们必须偷偷地加入 a($!)以确保suc n被热切地评估：

lise' :: (b -> b) -> ((b -> b) -> (b -> b))
lise' suc = \g -> \n -> g $! suc n

现在我们可以定义一个严格的左折叠（它是 to foldNatwhat foldl'from Data.Listis to foldr）：

foldNatL' :: b -> (b -> b) -> Natural -> b
foldNatL' zero suc n = foldNat id (lise' suc) n zero

最后还有一个重要的细节需要处理：如果我们在此过程中懒惰地构建 pair，那么让 fold strict 变得毫无用处，因为 pair 组件将继续懒惰地构建。我们可以通过使用($!)with(,)来在后继函数中构建对来解决这个问题。但是，我相信使用严格的 pair 类型会更好，这样我们就不必担心：

data SP a b = SP !a !b 
    deriving (Eq, Ord, Show)

fstSP :: SP a b -> a
fstSP (SP a _) = a

sndSP :: SP a b -> b
sndSP (SP _ b) = b

将!字段标记为严格（请注意，您无需启用BangPatterns即可使用它们）。

一切就绪后，我们终于可以有fib一个严格的左折叠：

fib' :: Natural -> Natural
fib' = fstSP . foldNatL' (SP 0 1) (\(SP a b) -> SP b (a + b))

PS：正如 amalloy 所说，您fac计算的是n^n而不是n！. 这可能是一个更好的问题留给一个单独的问题；无论如何，它的要点是阶乘更自然地表达为自然的变形，而不是简单的变质。（有关这方面的更多信息，请参阅 Jared Tobin 的Practical Recursion Schemes博客文章，更具体地说，是关于 paramorphisms 的部分。）

haskell - 如何使用自然数的折叠来定义斐波那契数列？

问题描述

解决方案

推荐阅读