haskell - 使用 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

这是我知道如何以表达我的问题的方式扩展列表定义的最佳方式。

所以我的问题是为什么这个列表扩展得这么快？这些天我对如何计算大 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——一个1。那么f q x就是1 + 1 = 2:

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

现在，我们已经在内存中计算了 tail fib 的头部，因此 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 ”从顶部开始”——在递归调用中，头部被简单地砍掉，尾部方便地从我们刚刚计算的值开始，现在可以在下一步中立即使用。)