Project Euler #2 Solution from the Haskell Wiki

Question

I've just started reading a little bit about Haskell and have only been coding a tiny bit which means I'm a complete Haskell newbie.

The Project Euler Problem #2 is as follows:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

My own first step to create fibonacci numbers was a naive (and slow/expensive) one. Having failed I went looking for solutions. The Haskell Wiki has a solution. There are several and I find the first one very elegant - but I don't fully understand it. This is my code (with the where/fibs construct split out for readability and tinkering)

p :: Integer
p = sum [ x | x <- takeWhile (< 4000000) fibs, even x]

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

main :: IO()
main = do
    print $ p
    -- BEWARE print $ fibs

When I run this with print $ fibs it just doesn't end, which is what I suspected, given that fibs just keeps calling itself and the condition to abort is part of the takeWhile call.

Looking just at fibs alone, it looks to me like the function already returned part of the list it will return but it's still adding more elements to be appended to the list and it never ends. Is this what one would call an Infinite List and it's probably also a Tail Recursion I suspect? How does the fibs function work?

Update

And of course I'm not the first one asking this. A very thourough explanation can be found elsewhere on SO.

This question has been answered very well over here: stackoverflow.com/questions/6273621/… — Erik Vesteraas
@ErikVesteraas thanks for the link, I searched specifically for euler related questions. — stackmagic

genisage genisage · Accepted Answer · 2014-10-21T22:34:50

the fibs function works by shifting a list left by one and adding it to itself.

You tell it that fibs = 1 : 1 : something, and from that it can tell that tail fibs = 1 : something. So zipWith (+) fibs (tail fibs) starts with 1+1=2.

Now haskell knows fibs = 1 : 1 : 2 : something and it can continue generating more terms for you ad infinitum.

Project Euler #2 Solution from the Haskell Wiki

1 Answers