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

How to define the fibonacci sequence using a fold for natural numbers?

我目前正在学习结构意义上的褶皱recursion/catamorphisms。我使用自然数的折叠实现了幂和阶乘。请注意,我几乎不知道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)

让类型来指导您。这是您的 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))

再看一下 fib 实现中的 go 帮助程序,我们可以注意到递归情况需要和 returns 一对 (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 的一个完美实现,但它与您编写的那个之间有一个主要区别:这是一个惰性右折叠([=87= 的规范) ] catamorphisms),而你的显然意味着严格的左折叠。 (是的,在这里使用严格的左折叠确实有意义:一般来说,如果你正在做的事情看起来像算术,你理想情况下想要严格的左折叠,而如果它看起来像构建数据结构,你想要惰性的右折叠)。不过,好消息是我们可以使用变质来定义几乎任何递归使用值的东西……包括严格的左折叠!在这里,我将使用 foldl-from-foldr 技巧的改编版本(有关列表情况的详细说明,请参阅 this question),它依赖于这样的函数:

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

这个想法是我们利用函数组合(\n -> g (suc n)g . suc 相同)以相反的顺序做事——就好像我们交换了 succgogo 定义的右侧。 lise suc 可以用作 foldNat 的后继参数。这意味着我们最终会得到一个 b -> b 函数而不是 b,但这不是问题,因为我们可以自己将它应用于零值。

因为我们想要 strict 左折,我们必须潜入 ($!) 以确保 suc n 被急切评估:

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

现在我们可以定义一个严格的左折叠(它是 foldNat 就像 Data.List 中的 foldl'foldr):

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

还有最后一个重要的细节需要处理:如果我们在整个过程中懒惰地构建一对,那么严格折叠几乎没有用,因为对组件将保持懒惰地构建。我们可以通过使用 ($!)(,) 在后继函数中构建对来处理这个问题。但是,我相信使用严格的对类型会更好,这样我们就不必担心了:

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))

P.S.: 正如 amalloy 指出的那样,您的 fac 计算 n^n 而不是 n! .这可能最好留给一个单独的问题;无论如何,它的要点是阶乘更自然地表示为自然数的同态,而不是普通的同态。 (有关更多信息,例如,请参阅 Jared Tobin 的 Practical Recursion Schemes 博客 post,更具体地说是有关同态的部分。)