How fibonacci function expand?

Question

I have a very simple fibonacci function:

fibs = 1 : scanl (+) 1 fibs

But I can't figure out how it's going to expand. As you can see, it's a recursive function.

The fibonacci sequence numbers are(start by one):

1, 1, 2, 3, 5, 8, 13, 21, n 

The second number (the number 1) on sequence above, for me it is not clear, why is 1 not 2.

Please explain me, how fibs is going to be expanded?

Update

I tried expand as follow:

fibs = 1 : scanl (+) 1 fibs

scanl (+) 1 [1](fibs) = 1 : (
                                case [1] of
                                    [] -> []
                                    x:xs -> scanl (+) (1+1) [1](fibs)
                            )

scanl (+) 2 [1](fibs) = 2 : (
                                case [1] of
                                    [] -> []
                                    x:xs -> scanl (+) (2+1) [1](fibs)
                            )

scanl (+) 3 [1](fibs) = 3 : (
                                case [1] of
                                    [] -> []
                                    x:xs -> scanl (+) (3+1) [1](fibs)
                            )   

As you can see, the tail is always return [1](fibs), that is of course wrong.
The last expression should be:

scanl (+) 3 [2](fibs) = 3 : (
                                case [2] of
                                    [] -> []
                                    x:xs -> scanl (+) (3+2) [3](fibs)
                            )   

But I could not image, how does it works.

Answer 1

A perspective that helped me realize what is happening in this sequence is to remove the recursion and construct it by hand. To illustrate this better, I will use a Fibonacci sequence starting with 2 and 3:

[2, 3, 5, 8, ...]

Here all the terms are different, so it is easier to distinguish between them.

First, no recursion is needed to produce the first two members:

λ> 2 : (scanl (+) 3 [])
[2,3]

That is, the first member is given and the second member 3 is the value given as initial accumulator for scanl.

So when recursion kicks in, the sequence is [2, 3]. At this point the value of the accumulator is 3 and the first term of the sequence is the next value consumed by scanl.

λ> 2 : (scanl (+) 3 [2])
[2,3,5]

Thus the next output is 3 + 2 = 5 as expected.

After this the value of the accumulator is 5 and the next value consumed by scanl is 3, so the next output is 8.

λ> 2 : (scanl (+) 3 [2, 3])
[2,3,5,8]

Hope this helps (someone).

Answer 2

We have

fibs = 1 : scanl (+) 1 fibs

and can lookup the definition of scanl to be

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

For the following analysis, we will simply think of scanlGo as scanl.

We want to see, how haskell evaluates the expression

  let fibs = 1 : scanl (+) 1 fibs

Full disclosure: As the expression is written, it doesn't get evaluated at all (ignoring possible implementation details).

Why is that? Haskell is lazy and expression are evaluated until they reach "Weak head normal form", which means, that an expression is evaluated until we get an resulting expression, which is normal form or which is a data constructor or an lambda awaiting an argument (i.e. a partially applied function).

So the value bound to the name fibs is already in weak head normal form, as it is an data constructor with arguments.

 1 : scanl (+) 1 fibs
-- ^ this is the data constructor

So to get haskell evaluate anything at all here, we need to prod it a little.

Let's start with

  tail fibs

you can't type that in ghci, as it will try to print it, which will further try to evaluate it ad inifinitum. So if you want to experiment with ghci, use

let t = tail fibs
head t

So how would the expression tail fibs be evaluated? It goes roughly like this:

    tail fibs
  = tail (1 : scanl (+) 1 fibs)
  = scanl (+) 1 fibs
  = 1 : case fibs of { [] -> []; x:xs -> scanl (+) (1 + x) xs ; }
  --  ^ data constructor

and here it stops, as we reached a data constructor. head $ tail fibs is now easily evaluatable, without the need to evaluate the case expression any further. This result will hopefully also be memoized, so haskell now knows, that the expression known as fibs can be evaluated to

1 : 1 : case fibs of { [] -> []; x:xs -> scanl (+) (1 + x) xs ; }

Lets ask for tail (tail fibs):

  tail (tail fibs)
= tail (1 : case fibs of { [] -> []; x : xs -> scanl (+) (1 + x) xs; }
= case fibs of { []-> []; x : xs -> scanl (+) (1 + x) xs; }
= scanl (+) (1 + 1) (tail fibs)
= 2 : case (tail fibs) of { [] -> [] ; x:xs -> scanl (+) (2 + x) xs; }
--  ^ data constructor

and here it stops again. Again the result will be memoized and haskell now knows, that the expression fibs, can be evaluated to:

1 : 1 : 2 : case (tail fibs) of { [] -> []; x:xs -> scanl (+) (2+x) xs; }

and now it goes on like that, if you ask for further elements, remember haskell won't evaluate the expression further, after reaching normal form or a data constructor or a partially applied function, if you don't ask for it.

old answer:

So basically it is

fibs = 1 : scanl (+) 1 fibs
fibs = 1 : 1 : scanl (+) 2 (tail fibs)
fibs = 1 : 1 : 2 : scanl (+) 3 (tail (tail fibs))
fibs = 1 : 1 : 2 : 3 : scanl (+) 5 (tail (tail (tail fibs)))
fibs = 1 : 1 : 2 : 3 : 5 : scanl (+) 8 (tail (tail (tail (tail fibs))))

In the evaluation of the next list element, scanl get evaluated. So we directly get the next element as the value handed to scanl as second parameter. For the then following element haskell stores the computation, which will always evaluate the second branch of the case, as we are always one element behind in consuming fibs. Here the next fibonacci number is calculated as f q x.

Of course it will not be some stacked succession of tail calls in the last parameter of scanl, but there will be some method of keeping the position in the list in a more direct way, as we already computed it. I used those stacked tail calls to enable an easier understanding.

PS: Additional answer to one the comments:

1: tail fibs = scanl (+) 1 fibs
2:           = scanl (+) 1 (1 : scanl (+) 1 fibs)
3:           = 1 : scanl (+) 2 (scanl (+) 1 fibs)
-- with the equation from line 1 we can do
4:           = 1 : scanl (+) 2 (tail fibs)

5: tail (tail fibs) = scanl (+) 2 (tail fibs)
6:                  = scanl (+) 2 (1 : scanl (+) 2 (tail fibs))
7:                  = 2 : scanl (+) 3 (scanl (+) 2 (tail fibs))
-- with the equation from line 5 we can do
8:                  = 2 : scanl (+) 3 (tail (tail fibs))

and so on.

PSS: In your try to expand it, you set fibs = [1] which is wrong. It is 1 : some computation, not yet done thanks to lazyness.

Answer 3

Maybe this will be more clearer:

-- scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
let fibs = 1 : scanl (+) 1 fibs

   fibs
=> 1 : scanl (+) 1 fibs
=> 1 : scanl (+) 1 (1:...)
=> 1 : 1 : scanl (+) (1 + 1) (tail $ 1:1:...)
=> 1 : 1 : scanl (+) 2 (1:...)
=> 1 : 1 : 2 : scanl (+) (2 + 1) (tail $ 1:2:...)
=> 1 : 1 : 2 : scanl (+) 3 (2:...)
=> 1 : 1 : 2 : 3 : scanl (+) (3 + 2) (tail $ 2:3:...)
=> 1 : 1 : 2 : 3 : scanl (+) 5 (3:...)
=> 1 : 1 : 2 : 3 : 5 : scanl (+) (5 + 3) (tail $ 3:5:...)
=> 1 : 1 : 2 : 3 : 5 : scanl (+) 8 (5:...)
=> 1 : 1 : 2 : 3 : 5 : 8 : scanl (+) (8 + 5) (tail $ 5:8:...)
=> 1 : 1 : 2 : 3 : 5 : 8 : scanl (+) 13 (8:...)
=> 1 : 1 : 2 : 3 : 5 : 8 : 13 : scanl (+) (13 + 8) (tail $ 8:13:...)
=> 1 : 1 : 2 : 3 : 5 : 8 : 13 : scanl (+) 21 (13:...)
=> 1 : 1 : 2 : 3 : 5 : 8 : 13 : 21 : scanl (+) (21 + 13) (tail $ 13:21:...)
=> 1 : 1 : 2 : 3 : 5 : 8 : 13 : 21 : scanl (+) 34 (21:...)

Answer 4

Scan and fold are similar except in one thing. In fold the result being the final value but in scan, it's a list of all the intermediate values up to the final one.
As we're concatenating first number onto the front of the list, the first fibonacci number will be 1. The second fibonacci number will also be 1 (the second argument to scan), after that every fibonacci number is the sum of the previous number (scan's running total) and the one before that.