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

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 2

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.