fibonacci_scan.hs

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


fibs = 1 : scanl (+) 1 fibs


-- STEP 1
---------
-- binds arguments of
-- scanl f q ls
-- to
-- f = (+)
-- q = 1
-- ls = [1,...]
-- intentionally using three dots "..." for the rest of the list
-- "..." is scanl (+) 1 fibs that is being evaluated, so we don't know yet the result, therefore the dots

-- showing the "result" in the case branch
fibs == 1 : 1 : scanl f (f q x) xs)
-- f = (+)
-- q = 1
-- x = 1 -- the first element of fibs
-- xs = rest of the fibs - is now consumed by one element so [1,1,...] is now [1,...]
fibs == 1 : 1 : scanl (+) ((+) 1 1) [1,...]
fibs == 1 : 1 : scanl (+) 2 [1,...]

-- STEP 2
---------
fibs == 1 : 1 : 2 : scanl f (f q x) xs
fibs == 1 : 1 : 2 : scanl (+) ((+) 2 1) [2,...]
-- fibs consumed by two elements, now it is [2,...]

-- STEP 3
---------
fibs == 1 : 1 : 2 : 3 : scanl f (f q x) xs
fibs == 1 : 1 : 2 : 3 : scanl (+) ((+) 3 2) [3,...]

-- STEP 4
---------
fibs == 1 : 1 : 2 : 3 : 5 : scanl (+) ((+) 5 3) [5,...]

-- the key is to realize that we always see only one element "ahead", but that is jsut what we need for the computation
-- once you get the hand of it, it actually makes perfect sense :)