如何使用自然数折来定义斐波那契数列? [英] How to define the fibonacci sequence using a fold for natural numbers?

问题描述

我目前正在从结构递归/同构性的意义上学习褶皱.我对自然数使用折线来实现幂和阶乘.请注意，我几乎不了解Haskell，因此代码可能很尴尬:

I am currently learning folds in the sense of structural recursion/catamorphisms. I implemented power and factorial using a fold for natural numbers. Please note that I barely know Haskell, so the code is probably awkward:

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

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

Next I wanted to adapt the fibonacci sequence:

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

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

With fib I have a pair as second argument whose fields are swapped at each recursive call. I am stuck at this point, because I don't understand the mechanics of the conversion process.

如注释中所述，我的fact函数是错误的.这是一个基于变态的新实现(希望如此):

As noted in the comments my fact function is wrong. Here is a new implementation based on a paramorphism (hopefully):

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，但带有类型签名:

Let the types guide you. Here is your foldNat, but with a type signature:

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的各个部分应如何放置:

Having another look at the go helper in your implementation of fib, we can note the recursive case takes and returns a (Natural, Natural) pair. Comparing that with the successor argument to foldNat suggests we want b to be (Natural, Natural). That is a nice hint on how the pieces of go should fit:

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

(我暂时忽略了严格性问题，但我会再讲一遍.)

(I am ignoring the matter of strictness for now, but I will get back to that.)

这还不是很fib，通过查看结果类型可以看出.不过，如Robin Zigmond所指出的那样，解决该问题没有问题.

This is not quite fib yet, as can be seen by looking at the result type. Fixing that, though, is no problem, as Robin Zigmond notes:

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

这时，您可能需要向后工作，并替换foldNat的定义，以说明这与显式递归解决方案的对应方式.

At this point, you might want to work backwards and substitute the definition of foldNat to picture how this corresponds to an explicitly recursive solution.

虽然这是fib的一个很好的实现，但是它与您编写的一个主要区别是:这是一个懒惰的正确对折(这是Haskell变形的规范)，而您显然是意味着严格的左折. (是的，在这里使用严格的左折确实是有道理的:通常，如果您所做的工作看起来像算术，则理想情况下您希望使用严格的左折，而如果看起来像在构建数据结构，则您希望是惰性的).好消息是，我们可以使用变形来定义几乎所有递归消耗值的东西...包括严格的左折！在这里，我将使用foldl-from-foldr技巧的改编版(请参阅此问题，以获取有关该问题的详细说明) (以列表为例)，它依赖于这样的功能:

While this is a perfectly good implementation of fib, there is one major difference between it and the one you had written: this one is a lazy right fold (as is the norm for Haskell catamorphisms), while yours was clearly meant as a strict left fold. (And yes, it does make sense to use a strict left fold here: in general, if what you are doing looks like arithmetic, you ideally want strict left, while if it looks like building a data structure, you want lazy right). The good news, though, is that we can use catamorphisms to define pretty much anything that consumes a value recursively... including strict left folds! Here I will use an adapted version of the foldl-from-foldr trick (see this question for a detailed explanation of that in the case of lists), which relies on a function like this:

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，但这不是问题，因为我们可以自己将其应用于零值.

The idea is that we take advantage of function composition (\n -> g (suc n) is the same as g . suc) to do things in the opposite order -- it is as if we swapped succ and go in the right hand side of your definition of go. lise suc can be used as the successor argument to foldNat. That means we will get a b -> b function in the end rather than a b, but that is not a problem because we can apply it to the zero value ourselves.

由于我们想让 strict 左折，因此我们必须潜入($!)以确保对suc n进行了急切的评估:

Since we want a strict left fold, we have to sneak in a ($!) to make sure suc n is eagerly evaluated:

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

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

Now we can define a strict left fold (it is to foldNat what foldl' from Data.List is to foldr):

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

还有最后一个重要的细节要处理:如果我们在构建过程中延迟构建对时，严格限制折叠几乎没有用，因为对组件将保持延迟构建.我们可以通过将($!)和(,)一起用于在后继函数中构建对来解决该问题.但是，我相信使用严格的对类型更好，这样我们就不必担心:

There is a final, important detail to deal with: making the fold strict is of little use if we are lazily building a pair along the way, as the pair components will remain being built lazily. We could deal with that by using ($!) along with (,) for building the pair in the successor function. However, I believe it is nicer to use a strict pair type instead so that we don't have to worry with that:

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即可使用它们).

The ! mark the fields as strict (note that you don't need to enable BangPatterns to use them).

一切就绪后，我们终于可以将fib作为严格的左折:

With everything in place, we can at last have fib as a strict left fold:

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

---

P.S .:如合金所示，您的fac计算的是 n ^ n 而不是 n！.最好将这个问题留给一个单独的问题.在任何情况下，其要点是阶乘更自然地表示为自然的同态，而不是普通的同构. (有关详情，请参见 实用递归方案 由Jared Tobin撰写的博客文章，更具体地说是有关同态的部分.)

---

P.S.: As amalloy notes, your fac calculates n^n rather than n!. That is probably a matter better left for a separate question; in any case, the gist of it is that factorial is more naturally expressed as a paramorphism on naturals, rather than as a plain catamorphism. (For more on that, see, for instance, the Practical Recursion Schemes blog post by Jared Tobin, more specifically the section about paramorphisms.)

这篇关于如何使用自然数折来定义斐波那契数列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！