Haskell is a functional programming language. The functional programming paradigm focuses on changing data through expressions that don’t have side effects. These expressions are often called pure functions. We’ll write a pure function that removes a particular element from a list in Haskell. Let’s break down the problem before jumping to the code.
Functional programming encourages us to define the problem in a more abstract way, independent of the concrete order of instructions. Often, it is helpful to break down the problem into smaller valid problems and solve them recursively.
Let’s take an example of a list [1,2,3,4]
, from which we want to remove element 3
. The answer should be [1,2,4]
.
Any recursive solution starts with a base case. The most simple removal is the head element of the list. If we want to remove the element that is placed at the beginning of the list, then we simply return the remainder of the list.
Now, to solve the general case where the element is not present at the head of the list, then that means we need to search the remaining list. We can see that this is a smaller problem because the list we now want to search is reduced. The problem now is removing element 3
from the remaining list [2,3,4]
.
Let’s assume our function will correctly solve this problem and we have access to its solution. The solution for this problem is [2,4]
.
Note that if we add the head of the original list (1
) to the above solution ([2,4]
), we solve the original problem! The list we get is [1,2,4]
.
Let’s look at a program in Haskell to remove an element from a list.
remove_one :: [Int] -> Int -> [Int] remove_one = \list -> \v -> case list of [] -> error "Element not found!" x:xs | v==x -> xs x:xs -> x:remove_one xs v main = print (remove_one [1,2,3,4] 3)
We write the remove_one()
function that removes a particular element from a list and returns the remaining list.
Line 1: The type annotation remove_one :: [Int] -> Int -> [Int]
shows that our function takes a list of integers and an integer element (element to be removed) and returns an integer list (the remaining list).
Line 2–3: Next, we have the function definition which shows that our function takes a list and an integer element v
. It is followed by a case expression that implements the recursive formulation of the problem.
Line 4: The first statement in the case expression shows that if the list is empty, we throw an error statement.
Line 5: x:xs
is a syntax in Haskell that destructures a list into its head element and the remainder list. The second case statement implements the base case. If the element to be removed is equal to the head of the list then we return the remainder of the list xs
.
Line 6: Finally, we implement the general case. We return the list which contains the head of the list and concatenate it with the list returned by the recursive call to remove_one()
which is passed the remainder xs
list. That’s it!
RELATED TAGS
CONTRIBUTOR
View all Courses