用Fibonacci数创建无限列表

Question

我做下一个作业=)我的任务是创建无限列表与斐波纳契数[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..] ]

它运作正常.:)这是正常的还是奇怪的？

Answer 1

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)

(另请参阅递归和corecursion之间的区别是什么？).

你的"第二次尝试",

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变量,使用元组而不是列表.