Big 0 of fibonacci number using scanl Haskell

Question

I'm trying to understand how a list that computes fibonacci is so fast in haskell.

The list definition is

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

This is the best way I know how to expand the list definition in a way that gets my question across.

So my question is why does this list expand so fast? I'm very hazy on how to calculate big-O these days but intuitively the way I expand it, it seems that the stack would grow astronomically huge with the way the function keeps expanding for each iteration of the fibonacci sequence. In fact, it looks to me that for every 3 numbers a new sub fibonacci sequence is created.

Yet, when I run the function it is very fast. Wiki says it is an O(n) function. https://wiki.haskell.org/The_Fibonacci_sequence#With_scanl

Is it that the compiler is doing special tricks so that it doesn't stupidly keep expanding the function like I do by hand?

Also, is there a special name for this type of recursion? I guess it's some type of tail-recursion, but I feel very fuzzy about this function.

Answer 1

The definition of scanl is (almost equivalent to):

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

So fibs expands to:

  fibs
= 1 : scanl (+) 1 fibs

We've computed the head of fibs in memory, so scanl knows its x -- a 1. Then f q x is 1 + 1 = 2:

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

Now, we have computed the head of tail fibs in memory, so scanl can fetch another x -- the second 1. Then f q x is 1 + 2 = 3:

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

The 2 we've just added to the list is simultaneously the head of the list scanl is accumulating down (currently tail $ tail fibs) -- we can retrieve it instantly!

The trick is that the computation of fibs doesn't restart from the first 1. Instead, scanl can look down the very list it's used in, and find the values it needs just in time! (I write tail $ tail fibs etc., but as we step through the computation, nowhere does scanl need to access the entirety of fibs "from the top" -- in the recursive call the head is simply chopped off, and the tail conveniently starts at the value we just calculated, which is now ready to use immediately in the next step.)