[Haskell-beginners] Using scanl for Fibonacci sequence

[Apoorv Ingle]

Hi Boon,

I guess it is difficult to comprehend what scanl exactly does here.
If you see the definition of scanl from hackage <http://hackage.haskell.org/package/base-4.9.0.0/docs/Prelude.html#v:scanl>

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl is similar to foldl, but returns a list of successive reduced values from the left:
scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, …]

Think of calculating a running sum of the first 10 positive integers, it can be easily computed using scanl
λ> scanl (+) 0 [1..10]
[0,1,3,6,10,15,21,28,36,45,55]

For fibonacci, you calculate the nth number by adding n-1th number and n-2th number.
Lets try to unfold the definition of fibs

fibs  = 1 : scanl (+) 1 fibs

now first element of fibs is by definition, ofcourse
1 (say x1)

second element of fibs will be (the first element generated by scanl)
1 (i.e. z — say x2)

Third element of fibs will be calculated as (the second element generated by scanl)
z `f` x1 = 1 + 1 = 2 (say x3)

Fourth element will be (and also the 3rd element generated by scanl)
(z `f` x1) `f` x2 = (1 + 1) + 1 = 3 (say x4)

Fifth element will be
((z `f` x1) `f` x2) `f` x3 = ((1 + 1) + 1) + 2 = 5 (say x5)

and so on..

The elegance is of course achieved because of the lazy evaluation of the infinite list
Hope this makes it some what clear.

Regards, 
Apoorv

> On 11-Oct-2016, at 23:23, Lai Boon Hui <laiboonh at gmail.com> wrote:
> 
> Hi All,
> 
> i am not very sure how this can work
> fibs = 1 : scanl (+) 1 fibs
> 
> Appreciate it if someone can guide me through by showing me a few steps of the function evaluation
> 
> -- 
> Best Regards,
> Boon Hui
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20161012/33a59cd5/attachment.html>