使用scanl Haskell的斐波纳契数的大0

Question

我试图理解如何在haskell中计算斐波纳契的列表是如此之快.

列表定义是

fibs = 1 : scanl (+) 1 fibs

 1 :: (1: scanl (+) 1 fibs) !! 0
:1 :: (1: scanl (+) 1 fibs) !! 1
:1+(1 :: (1: scanl (+) 1 (1: scanl (+) 1 fibs)!!0)!!2
:2+(1 :: (1: scanl (+) 1 (1: scanl (+) 1 fibs))!!1)!!3
:3+(2 :: (1: scanl (+) 1 (1: scanl (+) 1 (1: scanl (+) 1 fibs)!!0)!!2)!!4
:5+(3 :: (1: scanl (+) 1 (1: scanl (+) 1 (1: scanl (+) 1 fibs)!!1)!!3)!!5
:8+(5 :: (1: scanl (+) 1 (1: scanl (+) 1 (1: scanl (+) 1 (1: scanl (+) 1 fibs)!!0)!!2)!!4)!!6

这是我知道如何以一种可以解决我的问题的方式扩展列表定义的最佳方式.

所以我的问题是为什么这个列表扩展如此之快？这些天我对如何计算big-O非常朦胧,但直观地说,我扩展它的方式,似乎堆栈会随着函数在斐波那契序列的每次迭代中不断扩展的方式而变得天文数字巨大.事实上,在我看来,每3个数字就会产生一个新的亚斐波那契序列.

然而,当我运行该功能时,它非常快.Wiki说这是一个O(n)函数. https://wiki.haskell.org/The_Fibonacci_sequence#With_scanl

这是编译器正在做特殊的技巧,以便它不会像我手工那样愚蠢地继续扩展函数吗？

此外,这种类型的递归是否有特殊名称？我猜这是某种类型的尾递归,但我觉得这个函数非常模糊.

Answer 1

定义scanl是(几乎相当于):

scanl           :: (b -> a -> b) -> b -> [a] -> [b]
scanl f q ls    = q : (case ls of
                           []   -> []
                           x:xs -> scanl f (f q x) xs)

所以fibs扩展到:

  fibs
= 1 : scanl (+) 1 fibs

我们计算了fibs内存的头部,所以scanl知道它x- a 1.然后f q x是1 + 1 = 2:

= 1 : (1 : scanl (+) 2 (tail fibs))

现在,我们计算了tail fibs内存中的头部,因此scanl可以获取另一个x- 第二个1.然后f q x是1 + 2 = 3:

= 1 : (1 : (2 : scanl (+) 3 (tail $ tail fibs)))

在2我们刚刚添加到列表中同时列表的头scanl是向下积累(目前tail $ tail fibs) -我们可以立即恢复!

诀窍是计算fibs不会从第一次重启1.相反,scanl可以向下看它所使用的列表,并及时找到它所需的值!(我写tail $ tail fibs等等,但是当我们逐步完成计算时,无处scanl需要访问整个fibs"从顶部" - 在递归调用中,头部被简单地切掉,尾部方便地从我们刚刚开始的值开始计算好的,现在可以在下一步中立即使用.)