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

Question

我目前正在学习结构意义上的褶皱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)

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 帮助程序，我们可以注意到递归情况需要和 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 相同）以相反的顺序做事——就好像我们交换了 succ 和 go 在 go 定义的右侧。 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，更具体地说是有关同态的部分。）

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

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

haskell

recursion

fold

recursion-schemes

catamorphism