Removing duplicates from a list in Haskell without elem

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.


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)))