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

Question

我目前正在学习结构递归/变质意义上的折叠。我使用自然数的折叠实现了幂和阶乘。请注意，我几乎不了解 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)

Answer 1

让类型来指导您。这是您的 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 帮助程序，我们可以注意到递归情况采用并返回 (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 变形的规范) ，而你的显然意味着严格的左折。 (是的，在这里使用严格的左折叠确实有意义:一般来说，如果你正在做的事情看起来像算术，你理想情况下想要严格的左折叠，而如果它看起来像构建数据结构，你想要惰性的右折叠)。不过，好消息是我们可以使用变质来定义几乎任何递归使用值的东西……包括严格的左折叠!在这里，我将使用 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 相同)在相反的顺序——就好像我们在 go 定义的右侧交换了 succ 和 go。 lise suc 可以用作 foldNat 的后继参数。这意味着我们最终会得到一个 b -> b 函数而不是 b，但这不是问题，因为我们可以自己将它应用于零值。

因为我们想要一个strict left fold，我们必须潜入一个($!) 来确保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 博客文章，更具体地说是关于同态的部分。)