Removing duplicates from a list in Haskell without elem

Question

I'm trying to define a function which will remove duplicates from a list. So far I have a working implementation:

rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs)   | x `elem` xs   = rmdups xs
                | otherwise     = x : rmdups xs

However I'd like to rework this without using elem. What would be the best method for this?

I'd like to do this using my own function and not nub or nubBy.

Answer 1

Both your code and nub have O(N^2) complexity.

You can improve the complexity to O(N log N) and avoid using elem by sorting, grouping, and taking only the first element of each group.

Conceptually,

rmdups :: (Ord a) => [a] -> [a]
rmdups = map head . group . sort

Suppose you start with the list [1, 2, 1, 3, 2, 4]. By sorting it, you get, [1, 1, 2, 2, 3, 4]; by grouping that, you get, [[1, 1], [2, 2], [3], [4]]; finally, by taking the head of each list, you get [1, 2, 3, 4].

The full implementation of the above just involves expanding each function.

Note that this requires the stronger Ord constraint on the elements of the list, and also changes their order in the returned list.

Answer 2

Even easier.

import Data.Set 
mkUniq :: Ord a => [a] -> [a]
mkUniq = toList . fromList

Convert the set to a list of elements in O(n) time:

toList :: Set a -> [a]

Create a set from a list of elements in O(n log n) time:

fromList :: Ord a => [a] -> Set a

In python it would be no different.

def mkUniq(x): 
   return list(set(x)))

Answer 3

Same as @scvalex's solution the following has an O(n * log n) complexity and an Ord dependency. In difference to it, it preserves the order, keeping the first occurences of items.

import qualified Data.Set as Set

rmdups :: Ord a => [a] -> [a]
rmdups = rmdups' Set.empty where
  rmdups' _ [] = []
  rmdups' a (b : c) = if Set.member b a
    then rmdups' a c
    else b : rmdups' (Set.insert b a) c

Benchmark results

As you can see, the benchmark results prove this solution to be the most effective. You can find the source of this benchmark here.

Answer 4

I don't think you'll be able to do it without elem (or your own re-implementation of it).

However, there is a semantic issue with your implementation. When elements are duplicated you're keeping the last one. Personally, I'd expect it to keep the first duplicate item and drop the rest.

*Main> rmdups "abacd"
"bacd"

The solution is to thread the 'seen' elements through as a state variable.

removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = rdHelper []
    where rdHelper seen [] = seen
          rdHelper seen (x:xs)
              | x `elem` seen = rdHelper seen xs
              | otherwise = rdHelper (seen ++ [x]) xs

This is more-or-less how nub is implemented in the standard library (read the source here). The small difference in nub's implementation ensures that it is non-strict, while removeDuplicates above is strict (it consumes the entire list before returning).

Primitive recursion is actually overkill here, if you're not worried about strictness. removeDuplicates can be implemented in one line with foldl:

removeDuplicates2 = foldl (\seen x -> if x `elem` seen
                                      then seen
                                      else seen ++ [x]) []

Answer 5

Graham Hutton has a rmdups function on p. 86 of Programming in Haskell. It preserves order. It is as follows.

rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs) = x : filter (/= x) (rmdups xs)
rmdups "maximum-minimum"

"maxiu-n"

This was bothering me until I saw Hutton's function. Then, I tried, again. There are two versions, The first keeps the last duplicate, the second keeps the first.

rmdups ls = [d|(z,d)<- zip [0..] ls, notElem d $ take z ls]
rmdups "maximum-minimum"

"maxiu-n"

If you want to take the first and not the last duplicate elements of the list, as you are trying to do, just change take to drop in the function and change the enumeration zip [0..] to zip [1..].

Answer 6

It is too late to answer this question but I want to share my solution which is original without using elem and don't assume Ord.

rmdups' :: (Eq a) => [a] -> [a]
rmdups' [] = []
rmdups' [x] = [x]
rmdups' (x:xs) = x : [ k  | k <- rmdups'(xs), k /=x ]

This solution removes duplicates in the end of input, while question implementation deletes in the beginning. For example,

rmdups "maximum-minimum"
-- "ax-nium"

rmdups' "maximum-minimum"
-- ""maxiu-n"

Also, this code complexity is O(N*K) where N is the length of string and K is the number of unique characters in the string. N >= K thus, it will be O(N^2) in worst-case but this means that there is no repetition in the string and this is unlike since you try to delete duplicates in the string.

Answer 7

I would like to add to @fp_mora answer that on page 136 of Programming in Haskell there is another slightly different implementation:

rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x : xs) = x : rmdups (filter (/= x) xs)

It was easier for me to wrap my head around this one.

Answer 8

Using recursion-schemes:

import Data.Functor.Foldable

dedup :: (Eq a) => [a] -> [a]
dedup = para pseudoalgebra
    where pseudoalgebra Nil                 = []
          pseudoalgebra (Cons x (past, xs)) = if x `elem` past then xs else x:xs

While this is certainly more advanced, I think it is quite elegant and shows off some worthwhile functional programming paradigms.

Answer 9

You can use this compress function too.

cmprs ::Eq a=>[a] -> [a]
--cmprs [] = [] --not necessary
cmprs (a:as) 
    |length as == 1 = as
    |a == (head as) = cmprs as
    |otherwise = [a]++cmprs as

Answer 10

Using dropWhile also works, but remember to sort the list before using this

rmdups :: (Eq a) => [a] -> [a]
rmdups [] = []
rmdups (x:xs) = x : (rmdups $ dropWhile (\y -> y == x) xs)

Answer 11

remdups xs = foldr (\y ys -> y:filter (/= y) ys) [] xs

this apply the function to the first element and the list cnstructed recursively in the same way. at the first iteration basically you create a list where you only know the first element, and the rest of the list is constructed in the same way (adding the element to the list), and then is filtered to remove the item that specific cycle is adding.

So every iteration adds an element (call it X) to the list and filter the list removing all elements =X

Answer 12

...or by using the function union from Data.List applied to itself:

import Data.List

unique x = union x x

Answer 13

remove_duplicates (x:xs)
  | xs == []       = [x]
  | x == head (xs) = remove_duplicates xs
  | otherwise      = x : remove_duplicates xs

You could try doing this. I've merely replaced 'elem' with my own implementation. It works for me.