How to check if an element is present in a list in Haskell

What is a list?

In Haskell, a list is a data structure that stores multiple items of the same type. Haskell lists are implemented as linked lists.

[1,2,3] -- A list of integers
['a', 'b', 'c'] -- A list of characters

How to check if a list contains an element

We can check if a list contains a particular element by following the steps below:

  1. Separate the element at the head of the list from the rest of the list.
  2. Check if the element at the head matches the element we want to find.
  3. If the two elements do not match, recursively perform steps 1 and 2 with the remaining list until either the element is found, or all elements within the list have been checked.

The code below demonstrates the process:

contains :: Eq a => a -> [a] -> Bool
contains = \elem -> \myList ->
  case myList of
    [] -> False -- if all elements checked, return False
    x:xs | x == elem -> True -- If head matches elem, return True
    _:xs -> contains elem xs -- Check for element membership in remaining list
-- call function to check if a list contains an element
main = print(contains 2 [1,2,3], contains "c" ["a", "b"])

Explanation

In the code above:

  • In line 1, we declare a function called contains that accepts a list and an element as arguments and returns a Bool. The placeholder a indicates that the list and element to search may be of any data type, but the data types of both the list elements and the element to search must be the same. The Eq class ensures that the function only accepts arguments such that the elements are comparable.
  • In line 2, contains takes an element called elem and a list called myList as parameters.
  • In line 3, we use a case-of statement to check different cases for myList.
  • Line 4 defines the base case for the recursive function. If myList is empty, then elem cannot be present in the list, so the function returns False.
  • Otherwise, in line 5, myList is split into two parts, i.e., the element at the head and the rest of the list through the expression x:xs. If x matches elem, then we can conclude that myList contains elem and the function returns True.
  • If x does not match elem, then we need to check if elem is present in the remaining part of myList. Therefore, in line 6, we make a recursive call to contains with elem and xs as the parameters.
  • We call the contains function twice in line 8. The first function call checks if the element 2 is present in [1,2,3]. Consequently, the contains function returns True. The second function call checks if the element "c" is present in ["a", "b"]. Since this list does not contain "c", the function returns False.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)