2

我做我的下一个作业 =) 我的任务是用斐波那契数创建无限列表 [0,1,1,2,3,5,8..] 我可以使用 Prelude 中的任何函数。

我的尝试：

fibs2 :: [Integer]
fibs2 = reverse $ foldr f [1,0] [0..]
  where 
        f _ (x:y:xs) = (x+y):x:y:xs

此函数仅适用于有限列表，例如 [0..100]，它给出了无限列表：

*** Exception: stack overflow

我做错了什么？如何制作“懒惰”功能？

更新 我的第二次尝试：

fibs4 = 0:[ b | (a, b) <- scanl (\(x,y) _ -> (y,x + y)) (0,1) [0..] ]

它工作正常。:) 这是正常的还是奇怪的？

4

2 回答 2

7

foldr（使用严格的组合函数）将参数列表解构到最后，然后通过用户提供的组合函数重新组合它f：

foldr f z [a,b,c,...,y] = f a (f b (f c (.....(f y z).....)))

在你的情况下，

fibs2 = reverse $ foldr (\_ (x:y:xs) -> (x+y):x:y:xs) [1,0] [0..]

foldr这里永远不会产生任何输出。但这并不是因为缺乏尝试：它非常努力地递归无限列表以寻找它的结尾，因为它的组合功能是严格的（它在构造自己的结果之前匹配 ' 的其余foldr输出）。(x:y:xs)

Foldr用严格的组合函数表示递归，递归必须有它的基本情况，才能停止。您想到的是以下内容：

fibs2 = reverse $ snd $ until (null.fst) 
         (\(_t:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])

这显然是非终止的。ts只是表达时间的流逝。我们可以尝试查看其执行的整个历史，将其重写为

fibs2 = reverse $ snd $ last $ iterate
         (\(_t:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])

当然，无限列表中没有最后一个元素。但我们现在至少可以看到所有的中期结果：

> mapM_ (print.reverse.snd) $ take 11 $ iterate 
          (\(_:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])
[0,1]
[0,1,1]
[0,1,1,2]
[0,1,1,2,3]
[0,1,1,2,3,5]
[0,1,1,2,3,5,8]
[0,1,1,2,3,5,8,13]
[0,1,1,2,3,5,8,13,21]
[0,1,1,2,3,5,8,13,21,34]
[0,1,1,2,3,5,8,13,21,34,55]
[0,1,1,2,3,5,8,13,21,34,55,89]

因此，与其等到最后一个列表被构建（永远不会）然后再反转它，为什么不在我们进行时生成它的元素呢？无论如何，这一切都已经存在了。每个中间结果的最后一个元素，颠倒过来——不就是它的第一个元素吗？

> take 11 $ map (head.snd) $ iterate 
          (\(_:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])
[1,1,2,3,5,8,13,21,34,55,89]

整齐，嗯。那么我们真的需要我们的显式计时器吗？我们是否需要拖动前一个中间结果的整个尾部，还是只需要它的前两个元素？

fibs = map (head.tail) $ iterate (\[x,y] -> [x+y,x]) [1,0]

对恒定长度列表使用元组会更简洁一些。所以你看到我们已经到达了其中一个规范定义，

fibs = g (1,0)  where  g (a,b) = b : g (a+b,a)

（另请参阅递归和核心递归有什么区别？）。

你的“第二次尝试”，

fibs4 = 0:[ b | (a, b) <- scanl (\(x,y) _ -> (y,x + y)) (0,1) [0..] ]

如您所见，实际上与上述非常接近。scanl在时间计数列表上仅相当于iterate。所以它相当于

fibs4a = [a | (a,b) <- iterate (\(a,b) -> (b, a+b)) (0,1)]

我们在上面的推导中看到了它作为一个map变体，使用元组而不是列表。

于 2013-05-06T06:01:44.263 回答
3

是的，你不能反转一个无限数组。

看看这个：

0,1,1,2,3,5,8,13,21,...
  0,1,1,2,3,5,8, 13...   +
----------------------
0,1,2,3,5,8,13,21,...

从我尝试展示如何使用自身生成斐波那契数列的关系中可以看出，这很容易！您将zipWith使用加法函数将斐波那契及其尾部！

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

对于更多细节，这里是上述内容的扩展。

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fibs = 0 : 1 : zipWith (+) 0:1:? 1:?
fibs = 0 : 1 : (0+1) : zipWith (+) 1:? ?
fibs = 0 : 1 : 1 : zipWith (+) 1:1:? 1:?
fibs = 0 : 1 : 1 : 2 : zipWith (+) 1:2:? 2:?
fibs = 0 : 1 : 1 : 2 : 3 : zipWith (+) 2:3:? 3:?

ad infinitum...?代表一个thunk，一个尚未评估的 Haskell 计算。

于 2013-05-05T22:53:10.357 回答