How to remove duplicates from a list in Haskell

Haskell is a purely functional programming language with strong typing and lazy evaluation. When it comes to removing duplicates from a list, multiple approaches are available. One option is to utilize the Data.Set module for removing duplicates. Alternatively, you can create your own custom functions that are specifically designed to remove duplicates.

We will look at two different methods: using the Data.Set module and creating a custom function with the help of filterThe filter function in Haskell is used to select elements from a list that satisfy a given rule. function.

Removing duplicates with Data.Set

We can use the Data.Set module to remove duplicates from a list. This module offers a built-in function that converts the list into a set. Duplicates are automatically removed during this conversion because sets only store distinct elements. Then we convert the set back into a list, effectively eliminating all duplicates present in the list.

• Line 1: The code imports the necessary functions fromList and toList from the Data.Set module in Haskell.

• Line 3: The removeDuplicates function is defined with a type constraint (Eq a, Ord a) => [a] -> [a], indicating that it works for any type a that is both equatableIn Haskell, "equatable" means that values of a type can be compared for equality using the equality operator (==). (Eq a) and orderableIn Haskell, "orderable" means that values of a type can be compared and ordered using comparison operators such as <, >, <=, and >=. (Ord a).

• Line 4: The function removes duplicates from a given list by converting it to a set using fromList and then converting it back to a list using toList.

• Lines 6–13: In the main function, an example input list [1, 2, 3, 4, 3, 2, 1] is defined. The program then prints the original input list and the resulting output list after removing duplicates.

The algorithm's time complexity is $O(n)$ because it depends on the number of elements, n, in the input list. This complexity arises from converting the list to a set and then back to a list. The space complexity is also $O(n)$ in the worst case due to the storage required for the set and the resulting list.

Removing duplicates using filter

We can use filter function which is a built-in function in Haskell that doesn't require any module imports. It allows us to filter elements from a list selectively based on a specified condition.

We will use the filter as a helper function which will operate on the parent function, which will be called recursively, continuing to remove duplicates until all duplicates are eliminated or an empty list is encountered.

Code

The following code snippet demonstrates the implementation of removing duplicates using Haskell. It includes a main function and a parent function called removeDuplicates, which uses the filter function to eliminate duplicate elements.

• Line 1: The removeDuplicates function takes a list [a] as input and returns a list [a] as output. The Eq a constraint specifies that the elements of the list must be comparable for equality.

• Line 2: The first line states the base case: if the input list is empty ([]), the result is also an empty list ([]). This serves as the termination condition for the recursion.

• Line 3: It matches the input list (x:xs) into its head element x and the remaining tail xs. The result is constructed by appending x to the output of recursively calling removeDuplicates on the filtered tail xs.

  • The filter function is used to remove elements from xs that are equal to x. The expression (/= x) is a function that checks if an element is not equal to x. So filter (/= x) xs removes all occurrences of x from xs.

• Lines 5–12: The main function is responsible for creating an input list, applying the removeDuplicates function to it, and printing both the input and output lists using putStrLn and print functions.

The algorithm has nested recursive calls, with each call potentially traversing the remaining list elements using the filter function. This results in a time complexity of $O(n^{2})$, where n is the number of elements in the list. The space complexity is linear, represented as $O(n)$.