我做下一个作业 =) 我的任务是用斐波那契数 [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..] ]
它工作正常。 :) 这是正常的还是奇怪的?
最佳答案
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
这里从不产生任何输出。但这并不是因为缺乏尝试:它非常努力地向下递归无限列表以寻找它的末端,因为它的组合函数是strict(它匹配 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)
(另见 What's the difference between recursion and 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
变体,使用元组而不是列表。
关于list - 使用斐波那契数列创建无限列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16386719/