Title: Sum of Fibonacci numbers
Tags: haskell;fibonacci
Question: I'm rather new to Haskell. The problem is to find the sum of all even Fibonacci numbers not greater than 4 million. I can't use lists.
If I understand correctly, the below solution is wrong, because it uses lists:
my_sum = sum $ filter (odd) $ takeWhile (< 4000000) fibs
Where fibs is the list of all Fibonacci numbers.
Somehow, I find it difficult not to think in Haskell in terms of lists. Could anyone guide me to a solution to this problem?
Regards
If anyone is interested, I've solved this problem. Here is the code (very clumsy-looking, but works nevertheless):
findsum threshold = findsum' 0 1 0 threshold
findsum' n1 n2 accu t
| n2 &gt; t    = accu
| odd n2    = findsum' n2 n3 accu t
| otherwise = findsum' n2 n3 accu2 t
n3 = n2 + n1
accu2 = accu + n2
Comment: Why can't you use lists?

Comment: @mjboggess: I wrote a solution based on lists. I'm looking for tips on how to do that without lists.

Comment: Not homework - Project Euler. I just did this exact problem the other day.

Comment: Maybe his teacher is cribbing from Project Euler, then adding constraints. :)

Comment: I don't know why you say your first solution is "wrong".  I would consider it to be exactly the idiomatic and natural Haskell solution (OK, the parentheses around `odd` are unnecessary).

Comment: @Rafal - but why? In Haskell, with a suitable definition of fibs- even though there is a list, it is lazy. You're better off letting all that wonderful machinery do it's job and express solution directly. If fibs is defined correctly, no actual list will ever exist in memory!

Comment: Is this homework? What have you tried already?

Here is the accepted answer: You might find it easier to build this in excel and then figure the code out from there.  It is pretty easy to do this in excel. Just put 1 in the first cell and put 1 just below it. Then make every cell below that add the two above it. (ie, cell a3 contains =A1+A2). Make the next column contain only even values "ie, if(mod(a3,2)==0,a3,0)". Next, put your running sum in the third column.  Based on that you should be able to come up with the recursive solution.
Another way is to start with the problem. You only want a total which screams for an accumulator.
sumFib 75b5:f2c1:f5d7:b954:8dc3:cee9:baf:a8c0 Integer -&gt; Integer
sumFib threshold = sumFib' 1 1 0 threshold
sumFib' 75b5:f2c1:f5d7:b954:8dc3:cee9:baf:a8c0 Integer -&gt; Integer -&gt; Integer -&gt; Integer -&gt; Integer
sumFib' n1 n2 acc threshold
You can see the signatures of my functions above. I built a pretty front end that takes a  threshold (4,000,000) to decide when to quit building fibonacci numbers. Then I pass this plus the first 2 fibonacci numbers and an accumulator into the worker function "sumFib" which does the recursion. Voila...the answer, "4613732", without a list....
n1 is the n-1 fibonacci number and n2 is the n-2 fibonacci number.
Hope that helps.
EDIT: here is my full solution:
sumFib 75b5:f2c1:f5d7:b954:8dc3:cee9:baf:a8c0 Integer -&gt; Integer
sumFib threshold = sumFib' 1 1 0 threshold
sumFib' 75b5:f2c1:f5d7:b954:8dc3:cee9:baf:a8c0 Integer -&gt; Integer -&gt; Integer -&gt; Integer -&gt; Integer
sumFib' n1 n2 acc threshold
| n1 &gt; threshold = acc
| otherwise = sumFib' (n2+n1) n1 newAcc threshold
where newAcc = if n1 `mod` 2 == 0
then n1 + acc
else acc
Comment for this answer: Glad to help! It was a fun break from writing java :)

Here is another answer: Again, a non-example for how useful computers can be:
You can do this without a computer!
1st observation: Every third Fibo-number is even, the first even Fibo-number is F_3=2
Indeed: odd+odd=even; odd+even=odd; even+odd=odd, which already closes the circle
2nd observation: F_3 + F_6 + F_9 + ... + F_{3k} = 1/2 (F_{3k+2} - 1)
By Induction: F_3 = 2 = 1/2 (5 - 1) = 1/2 (F_5 - 1)
F_3 + F_6 + ... + F_{3k+3} = 1/2 (F_{3k+2} - 1) + F_{3k+3} = 1/2 (F_{3k+2} + 2F_{3k+3} -1) = 1/2 (F_{3k+4} + F_{3k+3} -1) = 1/2 (F_{3k+5} -1)
3rd observation: The sum will have 1333333 summands, the last one being the 3999999-th Fibo-number.
4th observation: F_n = 1/sqrt(5) * (phi^n - (1-phi)^n)
Proof by Wikipedia
Now, we can put the parts together:
F_3 + F_6 + ... + F_3999999 = 1/2 (F_4000001 - 1) = 1/2 1/sqrt(5) (phi^4000001 - (1-phi)^4000001) - 1/2 = int(1/2 1/sqrt(5) phi^4000001)
Here int is the integer part. The last step works, because -1 < 1-phi < 0 and so (1-phi)^4000001 nearly vanishes. You might want to use a calculator to get a numerical value.

Here is another answer: You can do this without a list, with a recursive solution, using continuation-passing style.
BTW running through all the fibonacci numbers and filtering out the odd ones is the slow way to solve this problem.
Comment for this answer: Thanks for the link. I will check it.

{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 3, 'CommentCount': 7, 'ContentLicense': 'CC BY-SA 2.5', 'CreationDate': '2010:00:05/05/10', 'FavoriteCount': 1.0, 'PostTypeId': 1, 'Tags': '<haskell><fibonacci>', 'Title': 'Sum of Fibonacci numbers', 'ViewCount': 3065, 'id': 2776685, 'user_AboutMe': None, 'user_AccountId': 611094.0, 'user_DisplayName': 'Rafal', 'user_Reputation': 51.0, 'user_Views': 5.0, 'user_id': 331881.0}}