Occurs check: cannot construct the infinite type: a = [a]

Question

I've been trying to do the 2nd Project Euler problem in haskell but I've been getting: Occurs check: cannot construct the infinite type: a = [a]

fibonacci 0 _ = 0
fibonacci 1 _ = 1
fibonacci x xs = (xs!!(x-2)) + (xs!!(x-1))

fibonaccisLessThan = takeWhile(<40) $ foldr fibonacci [] [0..]

sumOfEvenFibonaccis = sum $ filter even $ fibonaccisLessThan

main = putStrLn $ show $ sumOfEvenFibonaccis

Can someone tell me why?

Answer 1

Think about lines one to five. What do you want to achieve? You want to get a lazy list of Fibonaccis. But your approach is very strange. I don't see through your code, but I think I have an idea about what you try to do. Try to give your functions type-signatures, then you will see quickly, what's going wrong.

Here is a shorter way:

Think of short cutting your approach. Let's try to define a lazy list of Fibonacci numbers:

fibs = undefined

So, what now? The first thing we know, is that the first two elements are 0 and 1:

fibs = 0 : 1 : undefined

And the rest? It is fibs added with a shifted version of fibs. Look at this. zipWith f combines a list with another list using a function f:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

And here we are. That's all.

Answer 2

The reason for your error message is that the function fibonacci returns a number, nevertheless, you use it at line 5 as if it would return a list of that same kind of number.

This causes the type checker to try to unify a type "a" with the type "[a]" and this gives the occurs check error.

Think about it: where in your program is the list actually constructed? You know, there should be a : operator applied somewhere, directly or indirectly, but it isn't. Therefore, in your program, the list of fibonacci numbers is entirely fictional.