Hacker News new | past | comments | ask | show | jobs | submit login

As an alternative to the zipWith method of calculating the Fibonacci series, you can use scanl, resulting in (in my opinion) an even more elegant version:

    fibs = fix $ (1 :) . scanl (+) 1



Joining the other commenter, only 70% of the article reached this recipient's brain.

I would appreciate if you could help me fry it completely by offering a little more than an even shorter one-liner using a function I just read about the first time. Please?


I don't know if this will add much to the article, but let's go over things step by step.

scanl is the same as foldl, save for the fact that it outputs a list of all intermediate values. So where

    foldl (+) 0 [1..10]
would output 55,

    scanl (+) 0 [1..10]
would output [0,1,3,6,10,15,21,28,36,45,55].

(1 :) means prepend a 1 to the list it is given. The function that is passed as an argument to fix therefore returns a 1 followed by the successive summation values of its argument.

fix just infinitely applies its argument to itself, i.e.

    fix f = f (fix f)
In any strict language this would ofcourse just result in an infinite loop, but fortunately Haskell has lazy evaluation. So if we evaluate the list, for example with

    take 5 fibs
the following happens:

Haskell wants the first list element. The first element of (1 :) . scanl (+) 1 is 1, so there's no need to evaluate the scanl part yet. Now we need the second element. scanl first returns its accumulator, so that's another 1. For the third list element scanl needs the first element of its argument for the addition, so now we get to the recursive application. As before, the first element of (1 :) . scanl (+) 1 is 1, so the next element is 1 + 1 = 2. This 2 is then added to the next element, which is another 1, resulting in 3. Finally, we add 3 to the third element, giving 5. We now have five elements, which is what we requested, so the result will be [1,1,2,3,5].

I hope this helped a little. If you have any other questions, just let me know.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: