Determine if value is an element of a list in Haskell

Question

I'm trying to write a function that will determine if an element exists in a list, both of which being provided by the user. I think a recursive solution is best. This is what I have:

isElement :: a -> [b] -> Bool
isElement a [] = False
isElement a (x:xs) = if a == x then True
                     else isElement a xs

But it can't compile. The error is "Couldn't match expected type -a' with actual type -b'". I don't know what this means or how to fix the problem.

Answer 1

You code technically works. It's the type signature that's giving you trouble here.

First, here's the working code:

isElement :: (Eq a) => a -> [a] -> Bool
isElement a [] = False
isElement a (x:xs) = if a == x then True
                     else isElement a xs

I changed two things:

1. The first thing to keep in mind when working with Haskell's linked lists (the datatype that uses []) is that they can only contain elements of the same type. However in your type signature, a ➞ [b] you specify that you require your first element to be of type a and the ones in your list of type b, different from a.

2. The second thing is to "enable" equality checks with generic types a and b, and GHC will give you a warning with the steps to follow in order to fix that:

   • No instance for (Eq a) arising from a use of ‘=='
     Possible fix:
       add (Eq a) to the context of
         the type signature for:
           isElement :: a -> [a] -> Bool
   

   So what it tells us is to specify that the a type can be compared!
   And this is fantastic because we can totally do this by giving that clue to the compiler with the (Eq a) => part in our code, that roughly translates to "given this property (Eq) of datatype a, [insert type signature here]". (feel free to correct me here, people of StackOverflow!)

Your code works, and reimplementing functions with this kind of explicit recursion is how I learned how it worked in the first place, so don't hesitate to learn by rewriting the stuff you use, then check their sources on Hackage to see how real-world haskellers actually do it.

Have fun learning!