CODEWITHSUNDEEP
listhaskell
user1351008
user1351008

Reputation: 63

How do I fix an "Occurs check: cannot construct the infinite type" error?

I am trying to write a remove function, so that a user can type remove 'd' ["abc", "dc", "ad"] and get the output ["abc", "c", "a"].

My code is:

remove :: Eq a => a -> [[a]] -> [[a]]
remove a (x:xs) = filter (not.a) (x:xs)

But I get the following error message:

Occurs check: cannot construct the infinite type: a = [a] -> Bool
   When generalising the type(s) for `remove'

What does the error message mean, and how can I change the second line so it works?

Upvotes: 1

Views: 599

Answers (2)

Don Stewart
Don Stewart

Reputation: 137957

You state that the argument a is any type that supports equality.

But you then use it in a boolean expression: not . a.

The type of not is :: Bool -> Bool, so a must be of type Bool. But you already said that no, it was of type Eq t => t.

So that's a type error.

I think you mean to filter all elements that do not equal a, which would be:

remove a xs = filter (/= a) xs

However, your input is also a nested list, so you have to map the filter over the inner elements:

remove a xs = map (filter (/= a)) xs

Upvotes: 5

Daniel Fischer
Daniel Fischer

Reputation: 183888

The type of filter is

filter :: (a -> Bool) -> [a] -> [a]

so the first argument you pass to filter must be a function from the element-type of the list to Bool. In

remove :: Eq a => a -> [[a]] -> [[a]]
remove a (x:xs) = filter (not.a) (x:xs)

you say

  1. a has type a, and the list has type [[a]], i.e. the list-element type is [a], and
  2. not . a, the first argument to filter, has type [a] -> Bool.

Together, these imply

a = [a] -> Bool

but that is an infinite type.

You probably meant something like filter (not . (a `elem`)), or equivalently filter (a `notElem`), if the filter is meant to work on the outer list, or map (filter (/= a)) if you want to remove an element from each of the contained lists.

Upvotes: 6

Related Questions