Couldn't match expected type ‘[Integer]’ with actual type ‘Integer’

2
votes

I am working on creating a list of all the even numbers in the Fibonacci series which are less than or equal to 4,000,000. In Haskell, I've defined the Fibonacci series as:

fibs = 1 : 2 : next fibs
  where
    next (a : t@(b:_)) = (a+b) : next t

and am using the following list comprehension to construct my set:

[ x | x <- take 50 fibs, x `mod` 2 == 0, last x <= 4*10^6 ]

However, GHC is throwing a Couldn't match expected type ‘[Integer]’ with actual type ‘Integer’ error.

I understand that the predicate, last x <= 4*10^6, is responsible for the error. Inspired by hammar's answer here, my initial reaction was to ensure that 4*10^6 was the right type, so I tried rephrasing the predicate as last x <= toInteger 4*10^6 to no avail; same error. I also thought that maybe I needed to specify 4*10^6 as a singleton (i.e. [4*10^6]), but no luck there either.

I'm struggling to understand what is exactly going on and how best to resolve the issue.

2
haskell

2 Answers

3
votes
sum [ x | x <- take 50 fibs, x `mod` 2 == 0, last x <= 4*10^6 ]

take 50 fibs is a list of Integer ([Integer]), and x is an element of that list (thus an Integer). last is a function which takes a list...

GHCi> :t last
last :: [a] -> a

... but you are passing an Integer to it. You don't need last to filter the elements in the list comprehension; just use:

sum [ x | x <- take 50 fibs, x `mod` 2 == 0, x <= 4*10^6 ]

By the way, given that you know that the numbers in fibs always increase, you can write your expression as:

-- (<= 4*10^6) is shorthand for (\x -> x <= 4*10^6)
sum [ x | x <- takeWhile (<= 4*10^6) fibs, x `mod` 2 == 0 ]
-- Three equivalent alternatives:
(sum . takeWhile (<= 4*10^6)) [ x | x <-  fibs, x `mod` 2 == 0 ]
(sum . takeWhile (<= 4*10^6) . filter (\x -> x `mod` 2 == 0)) fibs
(sum . takeWhile (<= 4*10^6) . filter ((== 0) . (`mod` 2))) fibs

That way you don't need the arbitrary limit of 50 elements.

2
votes
fibs :: [Integer]
take 50 fibs :: [Integer]

x <- take 50 fibs
x :: Integer

last :: [a] -> a
last x :: ???

Your list comprehension will typecheck if you remove last. I think what you meant to write is something more like

[ x | x <- takeWhile (<= 4*10^6) $ take 50 fibs, x `mod` 2 == 0 ]

though.