A check occurs: it is impossible to build an infinite type: a = [a]

Question

I try to complete the 2nd Euler project in haskell, but I get: 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 of lines one to five. What do you want to achieve? You want a lazy Fibonacci list. But your approach is very strange. I don’t see your code, but I think I have an idea of ​​what you are trying to do. Try to give your functions signature types, then you will quickly see what is going wrong.

Here is a shorter way:

Think about shortening 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 

But other? Added fibs with a shifted version of fibs . Look at it. zipWith f merges the list with another list using the f function:

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

And here we are. It's all.

Answer 2

The reason for your error message is that the fibonacci function returns a number, however, you use it on line 5, as if it were returning a list of the same number.

This causes the type check to try to unify type "a" with type "[a]", and it gives an execution check error.

Think about it: where is the list really created in your program? You know, there must be an operator: an operator, somewhere, directly or indirectly, but it is not. Therefore, in your program, the list of fibonacci numbers is completely fictitious.

Answer 3

To begin with, we first notice that the fibonacci has type Int -> [Int] -> Int , and that foldr is of type (a -> b -> b) -> b -> [a] -> b , therefore we cannot give fibonacci for foldr, since we cannot unify a-> b-> b with Int -> [Int] -> Int . An error message appears here.

To fix this, we need to change the fibonacci function. fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci) is the classic haskell way of this, 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 

Answer 4

Some general recommendations: if you get a strange type error, make sure you have type signatures in all top-level definitions. This ensures that your type error is indicated in the correct definition. However, your definition of fibonacci is strange.

Answer 5

Other answers already indicate where the error comes from and show a very compact and elegant "standard" definition of Fibonacci numbers in Haskell. Here is another way to define it, which may be more friendly for beginners:

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

The idea is to track not only the last, but also the last two Fibonacci numbers that can be made using pairs. Using this tricks is very easy to determine the recursive ratio.

We start with argument (0,1) and generate a list from this initial value using the next function on ond again: [(0,1),(1,1),(1,2),(2,3),(3,5)...] . Then it remains only to "discard" the second argument of the pairs that map fst $ ... .

[Update]

Another nice definition (working similarly to zipWith-Version):

 fibs = 0 : scanl (+) 1 fibs