Sum of Fibonacci numbers

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

EDIT:

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 > t    = accu
| odd n2    = findsum' n2 n3 accu t 
| otherwise = findsum' n2 n3 accu2 t
where
    n3 = n2 + n1
    accu2 = accu + n2

Answer 1

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 :: Integer -> Integer
sumFib threshold = sumFib' 1 1 0 threshold

sumFib' :: Integer -> Integer -> Integer -> Integer -> 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 :: Integer -> Integer
sumFib threshold = sumFib' 1 1 0 threshold

sumFib' :: Integer -> Integer -> Integer -> Integer -> Integer
sumFib' n1 n2 acc threshold
     | n1 > threshold = acc
     | otherwise = sumFib' (n2+n1) n1 newAcc threshold
            where newAcc = if n1 `mod` 2 == 0
                               then n1 + acc
                               else acc

Answer 2

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.