Re: [Haskell-beginners] Using scanl for Fibonacci sequence

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 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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners