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

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 开发者_C百科= takeWhile(<40) $ foldr fibonacci [] [0..]

sumOfEvenFibonaccis = sum $ filter even $ fibonaccisLessThan

main = putStrLn $ show $ sumOfEvenFibonaccis

Can someone tell me why?

---

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.

---

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.

---

Some general advice: If you get a strange type error, make sure you have type signatures on all top level definitions. This ensures that your type error will be reported in the right definition. That said, your fibonacci definition is weird.

---

Let us start by first noticing that fibonacci has type Int -> [Int] -> Int, and that foldr has type (a -> b -> b) -> b -> [a] -> b, so we can't give fibonacci to foldr since we can't unify a-> b-> b with Int -> [Int] -> Int. This is where the error message comes from.

To fix it we have to change the fibonacci function. fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci) is the classic haskell way of doing it, for more ways take a look at this haskellwiki page. Then all you have to do is:

sumOfEvenLessThen n = sum . filter even . takeWhile (<n)
main = print $ sumOfEvenLessThen 40 fibonacci

---

The other answers already point out where the error comes from, and show the very compact and elegant "standard" definition of Fibonacci numbers in Haskell. Here is another way to define it, which might be more beginner friendly:

fibs = map fst $ iterate next (0,1) where 
    next (x,y) = (y,x+y)

The idea is to keep track not only of the last, but of the last two Fibonacci numbers, which can be done using pairs. With this trick it's very easy to define the recursive relationship.

We start with the argument (0,1) and generate a list from this start value using the next function over ond over again: [(0,1),(1,1),(1,2),(2,3),(3,5)...]. Then the only thing left to do is to "throw away" the second argument of the pairs, which is done by map fst $ ....

[Update]

Another nice definition (working similar like the zipWith-Version) is:

fibs = 0 : scanl (+) 1 fibs